It's possible to do it - I used the sharing all the time to my Pocket PC before having a Wi-Fi access point here. It is most likely to be some small thing on the specific network configuration.

Also check any software firewall you have because they do interfere with the Bluetooth communications.