Not knowing your domain name, I can't query your DNS server to check your MX record. You could use a tool like nslookup to verify your mx record is available. An example interactive nslookup session follows:
> set query=mx
Next enter your domain name at the > prompt.
This should give you the mx record for domain.com, just replace domain.com with your domain name. If that all looks correct you might want to make sure that port 25 is open to your qmail server.
Edit....: You can telnet to yourdomain.com 25
to test if port 25 is open. Of course this would have to be from outside.