Backup a remote database, from my machine, to another server (SQL Server 2008)
This problem occurs because the network firewall filters Kerberos traffic.
  
  To resolve this problem, configure the network firewall so that TCP port 88 and UDP port 88 are not blocked for either domain.


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

Sorry for just quoting...

Another thing to check is to make sure that your Service Startup account for SQL Server has the rights to access the file share that you are backing up to.

In SQL Server Configuration in the instance name > Properties > Log On > Log On as Account Type.