How can I import contacts into iPhone from Palm Centro?
Have a look into SyncML, it was the only way i managed to get my contacts out of my decade old Nokia. 

I'm not sure what the iPhone uses as a contact manager on Linux (Would MobileMe be a good workaround?), but once you've got them out, it's a lot easier to import them into something else.

Google Sync is also worth a look and would avoid your desktop altogether.