I had exactly the same problem.
My connection via my account in outlook was working fine both at home & work until about the same time.
Both came back meaningful outlook error (0x800CC0E) as the original poster suffered.
Vodafone call centre doesn't seem too clued up, the on-line FAQ doesn't hold much hope & I can't find my original instructions on how to set up vodafone.net.nz in outlook (either locally or on vodafone NZ)
Any help appreciated