OK - had a rather long chat with an apple cs rep but no real solution come forward.
I did set up a hotmail account during the call however, and this might be key to the problem.
Basically, it looks like there is a delay in the iPhone mail app recognising from the server that additional security is required. Once you get the message asking you to add a passlock, this will then allow you to connect to the exchange server.
So.... I can't recreate this, however to resolve, my advice would be:
Set up email account as normal
Change the advance settings to fetch
Try and fetch mail (will probably get an error)
Set up a hotmail account
Make a few calls or a cup of tea or something (I would say it took about 5 minutes after I finished the call with apple)
If nothing's come up asking for you to add a passcode, delete it all and start again and repeat.
Hope this helps someone else