Mike,
>If you log onto the sql server computer using the same credentials that the MSSQLServer service uses, can you get to the file server?
Yup. Got a drive mapped logged in with the same username and everything.
>Another option would be to backup to the local HD and have a job that copies the backup devices to the network.
That is one option, if the space were available.
How about any 3rd party backup utilities which might overcome this problem?