Error message given after membership confirmation screen
I received a similar message when trying to create a 'Provides Membership to' relationship. If you go in the civicrm_membership table for that contact ID, you will see that the join_date, start_date and end_date fields are all NULL. Set them to the correct values and it should work.

This does not answer how you got into the situation in the first place, but in several months of running our site I have only seen this once, so I have to believe it's an intermittent problem.