I had the same problem when I first got my Magic , In the end I had to manually edit them one-by-one.

I found it much easier and faster to go to http://www.google.com/contacts -> Sign in using the same Google account as on your phone -> Then editing them on the PC -> It will then sync back to your phone and you should see them correctly edited

It's still a long tedious process but I found this way much easier than editng them individually via the phone

Carl