Yes, UAC strikes once again!
I soon found out that this is a known issue and how you should work around it. Basically you add a manifest to the exe requesting elevated privileges.
<assembly xmlns="urn:schemas-microsoft-com:asm.v1" manifestversion="1.0">
However, I couldn't get this working under a debugger !?! (The manifest is there as both exename.exe.manifest and exename.vshost.exe.manifest)
So, how is one supposed to debug a WCF server on Vista !?!