Where is the data for "Contacts Storage" located? Settings -> Applications -> All tells me that "Contacts Storage" uses 2.5MB which must be my contact data.

Since I had to revert to 4.03 after a faulty update to 4.1 my contacts seem inaccessible although the data seems to be there.

Could you please tell me where to find the associated data(base) for Contacts Storage? My phone is rooted.
And no, my contact data is not on GMail and I honestly don't know why...
The exact location of the contacts database might depend on your manufacturer's "customization". While "plain Vanilla Android" has them in /data/data/android.providers.contacts/databases, the stock ROM on my Motorola Milestone 2 e.g. uses /data/data/com.motorola.blur.providers.contacts/databases/contacts2.db instead. A raw mask to check for is /data/data/*.providers.contacts/databases/*.db. The file is in SQLite3 format, and can be browsed on your PC with e.g. SQLiteman or DB Browser for SQLite, which is available for Linux, Mac, and Windows alike. With this application you can browse the database in a graphical mode. Of course you also can use the command line sqlite3 client if you prefer.

Crucial point to directly access this database is that your device must be rooted -- a precondition you already meet, as your question states.

So you can either use a file manager to navigate to the database file, and copy it to your computer for investigation -- or directly pull it to your computer via adb pull. A third option would be to investigate it directly on your device, e.g. using the SQLite Manager or aSQLiteManager app.