Cannot resolve name - seems like propagation is not working

[Alf]

Hi all,

I changed DNS records for a domain recently. It's been about five days from 
then and it seems like name information is not propagating right through the 
Internet. Or maybe i'm doing something wrong.

I've checked that the registry for the domain (anestped.org) points to my name 
server (leon.lanza-ti.com) using the whois service. If i ask my name server 
for the domain, it resolves it right:

> anestped.org
Server:         leon.lanza-ti.com
Address:        80.25.96.213#53

------------
    QUESTIONS:
        anestped.org, type = A, class = IN
    ANSWERS:
    ->  anestped.org
        internet address = 80.25.96.213
    AUTHORITY RECORDS:
    ->  anestped.org
        nameserver = leon.lanza-ti.com.
    ADDITIONAL RECORDS:
    ->  leon.lanza-ti.com
        internet address = 80.25.96.213
------------
Name:   anestped.org
Address: 80.25.96.213

But it doesn't happen with others. For example:

> anestped.org
Server:         80.58.0.33
Address:        80.58.0.33#53

------------
    QUESTIONS:
        anestped.org, type = A, class = IN
    ANSWERS:
    AUTHORITY RECORDS:
    ->  org
        origin = tld1.ultradns.net
        mail addr = domadmin.ultradns.net
        serial = 2006071401
        refresh = 1800
        retry = 900
        expire = 604800
        minimum = 86400
    ADDITIONAL RECORDS:
------------
** server can't find anestped.org: NXDOMAIN

How should i interpret this answer?

My name server is resolving some other domains right, and the configuration is 
the same for this new one, so i guess that's not the problem. The only 
difference is that this new domain is a .org one, while others are .com

I've talked to registrar's people and they say it should be all right, and 
that their registry is ok. How can i really check?

What more should i test? How can i find out more? I would appreciate any help. 
Tell me if you need more about my config, etc.

TIA,

Alf