Those name servers must be able to resolve the records that you have in your domain, otherwise it will probably fail.
Where's your dns hosted for the domain? On your box? At your ISP?
Try something like...
dig yourdomain.com @126.96.36.199 any
dig yourdomain.com @188.8.131.52 mx
to query all records or just the relevant mail exchanger records for what you believe is set up. If that or the other addresses don't return any information, points to a DNS issue I reckon.