Are you using windows or a mac? My windows PC is slow to find my ipod; sometimes it takes 30 seconds. Also, it wont find my ipod if more than one user is logged on (I dont know why this is).
The first thing I would do is reinstall itunes (which you already did). Next I would go to apple.com and download the most recent ipod updater and connect my ipod and run that. That should clear things up.