I wonder what Torch OS you are running?
I have noticed a strange thing - with the new 450, I must have that installed on the machine for the tether to work - otherwise I get the error message.
This is different to when I had 337 installed - then I could use on any machine with Blackberry Desktop installed and no OS.
I am away at present, so am using my laptop. While away I decided to do the 450 upgrade. Once done, I uninstalled 450 off the laptop just to keep things nice and clean....and the tether failed! Reinstalled 450 and it works again!
PS the 450 OS install was quick and simple - working well after 2 days OK