WCF
Who did you register your domain through?
if it was TUCOWS then they hold the root record so they should be able to modify the record to point to new nameservers by just you supplying the new information
have a look at the following - Especially Section 3. REGISTRAR OBLIGATIONS.
ICANN is the internet policing agency for domain names and registrars..
http://www.icann.org/registrars/ra-a...-17may01.htm#3
3.2.2 Within five (5) business days after receiving any updates from the Registered Name Holder to the data elements listed in Subsections 3.2.1.2, 3.1.2.3, and 3.2.1.6 for any Registered Name Registrar sponsors, Registrar shall submit the updated data elements to, or shall place those elements in the Registry Database operated by the Registry Operator.
So if they are not giving you the time of day then get a legal rep and get a formal letter stating the above (quote loss of earnings if appropriate)