OK, Since a reformat and reinstall is a bit of an undertaking, I'm thinking there may be some additional things to try.
Have you ever done a bluetooth sync? I'm assuming you haven't.
I know I had issue doing a bluetooth sync until I installed PDANet. PDANet seems to install its own drivers (or at least seems like it enhances the existing drivers). Even if you're not interested in using it for what it's intended for--tethering your phone--I wold be interested to see what happens to your sync connection (both bluetooth and USB) after you install it.
They give yout a trail period--I think it's 15 days. May be worth trying it just to see what happens.
http://www.junefabrics.com/pdanet/index.php