Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I've been wanting this feature for ages too. I got so fed up waiting I wrote an app - check out "Play it Next" in the App Store. It lets you queue up songs, even if you start off listening to a song in the iPhone's own music app.
 
This would be nice. Actually, any kind of changes to the playlist editing mechanism would be more than welcome. It's a giant pain in the rear trying to add songs to playlists! One of the most backwards things in all of iOS in my opinion.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.