Getting a 'mailbox does not exist' message can be frustrating, we know. You just need to give it half an hour.
Mailbox password changes, webmail access and sending/receiving email via a mail client are all available as soon as your mailbox has been created.
However, it can take up to 30 minutes for our MX servers to accept new email for your new mailbox. If you receive a “Mailbox does not exist” bounceback to a new mailbox within 30 minutes of its setup, this should be nothing to worry about. It should resolve itself as soon as our MX configuration updates.