There does not seem to be a problem at our server end and I can get my emails using a laptop, etc.
That doesn't necessarily mean anything as the server addresses and protocols used between the phone's activesync and your laptop connection are most likely different.
I would contact your Exchange admins and verify the activesync settings.
Thank you Templeton,
It pointed me in the right direction and whilst active sync and the server all seemed to be fine, I reverted to the sadly tried and trusted technique of shutting down and restarting our server, and guess what? I found I was able to connect to exchange from my iPhone - computers eh!