I have 2 new 3 g phones that just started doing this. Everything was ok until I was attempting to sync/upload some photos from my iphone to iPhoto and something happened to lock up the sync. I had to force quit and ever since that time I have had a general sync problem with 2 3G iphones. Strangely enough an old 1st gen iphone does not have this problem.
I have deleted itunes and the apple mobile sync files that it installs and then reinstalled everything and still have the problem. The only thing that works is to leave the phone connected for a while (I have no idea how long, minutes at least) as I usually walk away and then come back later to find the phone recognized by itunes.