When trying to configure the TFS 2010 backup using the TFS Power Tools I kept running into teh following error message:
Account TFS\tfsadmin failed to create backups using path \\tfs-xxxxxxx.local\TFSBackups
The strange thin is that TFS\TFSAdmin has full permissions on both share and file system and that the share path doesn't contain any spaces (thanks for MSDN forums for pointing that out).
I tried backing up through the SQL Server Management Studio, and sure, there the backups fail too.
It turns out that while the backup job is started using the account specified in the Create Backup Wizard of the TFS Power Tools, SQL Server will try to write the files to the share using its own service account.
So in addition to whomever needs access to the share, you need to add the service account running SQL Server to that share as well. In this case it was running under NETWORK SERVICE, so adding MACHINENAME$ to the share's list of permitted users did wonders.