I went to customer 819…
Created a new contact (assuming that this what was missing and that a ship to contact wasn’t enough)…
Created a case (1510) and it saved first time.
So, it looks like you have to have a contact as well as a ship to contact, if that makes sense.
I’ve left that case open…so just check the contact i’ve created and edit the case.
Mark there is a bug (or maybe a feature) where it defaults to Contact 0 and if that contact isn’t valid you get that error. You can also just go to the contact field and clear it out before saving.