Setting the TRUSTWORTHY Property for the database was was the eventual fix:

http://support.microsoft.com/kb/913422

For more information about how to use the TRUSTWORTHY property of a database, see the following topics in SQL...

Thanks for the suggestion. I'll chase that up...

I've made the service account sa and local admin....

Not sure, but doesn't that mean it'll have every possible right.

Thanks guys

Yep the server has been rebooted.

Yes it is sa and local admin.

The other thing is, everything (including this job) was working fine until inplace upgrade.

If I run this same process under my own account also...

thanks for the reply...

Yes it does.

When I first looked at this database it did not have sa mapped as a login and I got the same error as above...