Usb tethering does not work but pdanet does
Android offers a standard usb-network adapter (implemented in software) to accomplish usb tethering.

The problem can be on the PC side or on the Android phone's side as well.

Some hints for debugging:


Do you see that usb network device on your PC if you enable tethering?
If so, do you get a DHCP offer from that "USB network card" on your PC?
Can you ping the phone gateway from your PC (usually ping 192.168.4.129)?
Can you resolve DNS entries (nslookup google.com)?
Can you ping a random host on the internet (eg. ping google.com)?


To view debug logs on the phone use a logcat viewer and see for obvious entries.

If the problem is your phone software and you're willing to void your warranty, the aftermarket CyanogenMod firmware also offers this functionality, as well as several other custom ROMs (your phone seems to be supported, according to CM's device overview).