I have just had the exact same problem today
I contacted BT my provider who changed the outgoing server number and this did the trick
Dont know who your service provider is but give them a call they may be able to help.
I just let Office do the settings for me and thats when the problem started
Hope this helps