So, I just sold my 3gs with baseband 5.16xx(so not unlockable) and bought an already JB/unlocked 3gs with baseband 5.13.04. Just before nuking and selling the old one, I backed it up with iTunes, iCloud, used Juicephone to make another backup to make sure I'd keep my texts, and of course got my pictures into iPhoto.

When I plug the new one into my Mac, it comes up on iTunes with 'Set up your iPhone'. It gives me 2 options 1, to 'Set up as new iphone' and 2, to 'restore from backup of (my old phone, old phone number, time of backup earlier today)'. BUT, I was told specifically by the guy selling me this new unlocked phone that I should NEVER restore from iTunes or cats and dogs will rain from the sky/it would not be unlocked anymore.

I was told by a friend to let iCloud backup my new phone after putting in the SIM, so I did that only so far. I now have my contacts, which is fantastic. I don't have my apps, my settings, my texts, etc. I can't drag my bought apps from iTunes onto this new iPhone. Not sure what to do!

I've searched elsewhere and a lot in these forums and can't find the same issue, let me know if I missed an obvious thread or there's some hope for me. thanks!

Hmmm, I've just found this post. Perhaps I can put my data onto the phone manually. That still won't get my iTunes to buddy up with this one though right?

You should be fine to restore from backup. If you do and start having battery life problems, etc., then let us know and there are a few fixes. It's true we don't recommend upgrading from 1.x to 5.x and restoring from backup the entire way, most times these days it's OK to restore from a backup. We do still recommend setting up as new as a troubleshooting step if you're encountering errors after you set the phone up, but it really shouldn't be that bad.