Oh crap, I am now seeing this too. How do I roll back to an old version? I have titanium backup installed and have been backing up religiously, but when I look, it seems like there is only version 5.8.0?
EDIT: crap I feel stupid. Only one version in titanium backup cuz I was running the free version - one backup max per app
If you go to Settings-Applications-Manage Applications (select All at top), then scroll down to Maps and select it, you should see a pick for "Uninstall Updates". I selected it and it removed the most recent update and I have all of the contacts appearing.
Every time you go to the Market it will show that Maps needs to be updated. Don't update it untill they come out with a fix. If you do you will have to do the above procedue again.
I uninstalled the "maps" update, and my navigator started working as usual. I also had to reboot my phone after the "maps" update uninstall. All is well in my world now. =) Thanks guys for pointing me in the right direction. =) Very happy!!!!