well, you will have a partition of 500MB you can't really use, so the best way is to not erase, go into cydia, type Cydia Eraser then you can use that
if cydia eraser doesn't work try Cydia Impactor (needs PC/Mac) and if that doesn't work then yes, you must restore