If you want to "go all the way" and convert the Phone contacts to Gmail contacts-
- Use JRocker's export contacts advice and export your contacts to a CSV file
- Copy the CSV file to your computer
- Open Gmail and Export your current contacts to a different CSV file (this is a backup)
If you are familiar with CSV files you can edit the CSV file from your phone in Excel (don't change the file format after editing) and make it so that just the new contacts are contained in it. You can then import them into Gmail.
I have seen posts about duplicate contacts appearing when syncing after this process so you might be prepared to deal with some duplicates but it sure beats hand inputing them all!

Let me know how it goes if you decide to do this. I can help you work some of it off-line perhaps.