Email account not working on new PAYG account

[#1]

Hi,
I opened a new Dial-Up PAYG account last night and I'm having problems with the email account. My Plus.net user name is alicemacdonald and so my email address should be alice@alicemacdonald.plus.com.
Sadly, if anyone tries to send a mail to this address they get a mail back with the following error code...

This is an automatically generated Delivery Status Notification
Delivery to the following recipient failed permanently:
    alice@alicemacdonald.plus.com
Technical details of permanent failure:
PERM_FAILURE: DNS Error: Domain name not found

I would really really appreciate a quick response on this problem, I need this email address to work today but I'm worried it's a more serious problem at Plus.net's end.
Any thoughts?

[#2]

Hi there,
I've just sent you a test email and can see it in your mailbox.
Are the mails you are trying to receive all coming from the same source?

[#3]

Thanks for the reply, I can indeed see a mail in my inbox now. How interesting. All the other mails we tried to send were from a Gmail account, perhaps that is the problem?
Really appreciate the test though, I'll do a little bit more investigation myself.

[#4]

I've refreshed your mailbox anyway, so a retest may prove successful. 
Let me know if not and I'll have a further look.