Just to cover the obvious here, in the control panel, the USB root hub driver is recognized and running, correct? Also, have you tried reinstalling the driver just to make sure it'* not a hardware problem?
Many times, the usb "card" will feel loose inside the laptop, but is normal and should still function properly.
If you have tried reinstalling the software, and make sure there are no interrupt request collisions, or port collisions, then I would go the replacement route.
Then again, if you still have a warranty, let them figure it out either way.