Right ok, so I presume the phone is O2 branded?
SEUS will check for latest O2 Branded firmware (of which there are none)
WotanServer/
DaVinci will let you unbrand your phone, costs about £6 for a credit and has a
newer firmware out than the one you're using.
As this phone was originally on O2 and has O2 branding, I can pretty much guarentee that its a settings/setup problem.
I'd scour the web for Vodafone K800 settings, or post on
Esato and see if anyone can help.