796 kpbs = about 99.5 KB/s. So it's definitely broadband.

It might be an idea to give them a call to ask why there should be problems using games or p2p software on their service; http://www.velocityonline.net/support.html
According to this they don't seem to be anti-p2p use http://www.velocityonline.net/techsupp/problems.html

Most broadband services require a modem/router to connect. I can only guess what you're using by-passes the need for such hardware. But such softw itself may be part of the problem. Check the options within it to see if it has NAT protection & UPnP options.