When I upgraded my 3Gs to iPhone 4 in 2010 and again last month when upgrading iPhone 4 to iPhone 5, I made a current backup of the old iPhone and immediately used that backup to restore my new iPhone. Everything transferred, including all text messages (even carrying over to the iPhone 5 the ones that had originally been on the iPhone 3Gs.) I had to restore from backup twice because initially I wasn't given the choice of using the most recent backup; after that first restoration, I clicked the dropdown arrow next to the iPhone name in iTunes & immediately restored again and was given the opportunity to choose the newest saved backup. Seamless & quick.
I always use iTunes, not iCloud.