Did you change the glue records as well?
Did you check your records on www.intodns.com
ps. Falko, regarding your howto about having our own nameserver with goodady, the servernames of our ns1 and ns2 must be in the parked option or hosted here option ?
I don't know the GoDaddy interface, I think it has changed since I wrote the tutorial, so I can't tell anything about it.