I just went through this (upgraded last week) and had no issues whatsoever. Fresh backup, new phone, restore. I lost the settings from a few apps (games, who cares for the most part), and had to transfer my tunes again, but the contacts came through perfectly. 4.3.3 3GS to a (then) 4.3.2 i4.
If ya still have the old phone, try backing up again, or syncing the contacts to outlook, etc. and that should work.