The entity that was created by the framework doesn't have a contact.ContactTypeId property. It automatically removed it and created the ContactType association inside the Contact entity.
The way to get it to work, as you suggested, is to create a ContactType object by querying the database and assigning it to contact.ContactType. For example:
Contact contact = dbContext.Contacts.Single(c => c.Id == 12345);
ContactType contactType = dbContext.ContactType.Single(c => c.Id == 3);
contact.ContactType = contactType;