How do I sync apps that I have bought on the iPhone?
I had this same issue after I recreated my iTunes library.  This may be totally off because it was about a month ago, but I think I did this:


canceled the sync
clicked on the iPod under devices or whatever (maybe I secondary clicked)
I think after I clicked (or secondary clicked) on it, there was an option to copy purchased items


Sorry this is so vague, it's been awhile :)

on edit:

I just tested this out by alt clicking iTunes, creating a new library, and connecting my iPod.  It's pretty much exactly how I described.


cancel the sync
secondary click the iPod on the left
click "transfer purchases"


Afterwards, you can sync, and everything will be erased and rewritten to the iPod.

I'm not sure why Apple makes this so confusing.  The only reason I can come up with is that they want people to have to repurchase stuff but that seems a little over the top even from Apple.