Make sure you have good 3G coverage when you're doing this.
If the problem persists:
What network are you on? From your profile looks like you're on Vodafone in UK. Then an alternative is to setup your e-mail online through your desktop computer by following this link:
https://bis.eu.blackberry.com/html?brand=vodauk
I presume you don't already have an account there, so click on Create New Account and follow the steps to setup your e-mail.