Does it sync SMS green bubble friend messages too or just blue iPhone friends?
And does it sync them up to the cloud on first install or does it only sync new ones from this point forward?
Any message SMS or iCloud will be sync'ed no matter how old.
Make sure you have a date in the "Last Sync:" under messages.
You can also check iCloud.com and see if there is sync data for your messages to be 100% sure.