Record type unavailable Cannot find default record type of the appropriate type.

I am seeing this error when trying to Convert a lead. I have checked the profile for the current user, and the default record types are both Contacts and Accounts are accessible. (I have selected Do Not Create Opportunity, though there are no opportunity record types).

The docs were no help at all, no results in Google for the error. Does anyone know what the solution is?