In the Contacts database, which is a SQLite database file.
Make sure all your contacts are Google (the 'type' of contact). If they aren't, see the Contacts section of
Backing up an Android Device to change them. Then go to
Google Contacts to fix things up. (To fix them up manually on the phone, you have to be rooted, know SQL and have a SQLite editor. It's much easier at the site.)