[cleverjake]

In itunes, just plug in your phone, and on the left navbar under devices, click the name and change it.

Make sure to sync it afterwards

[dchest]

It changes the name of the device that I see in iTunes in addition to hostname, isn't it?

[tmgrhm]

Or, if on iOS 5, just go into Settings > About and change it in there.