Try rebooting the phone - you wouldn't actually have to do that if I knew how to force your phone to purge its DNS cache, but I don't know how. You could do it through a terminal/command line app but it's way easier to reboot than for us to walk through that.
A guy at work last week was having problems with a website that turned out to be a DNS problem. Restarting the phone cleared the DNS cache.
Not sure about PDAnet, Verizon has gone back and forth on blocking tethering apps if you don't have a tethering plan.