Threat Management Gateway can't access share on NAS

My network looks like this:

DC   - SERVER01  - Windows Server 2008 SBS
TMG  - TMG01     - Windows Server R2 Standard
NAS  - DATASTORE - Cisco NSS6000

All machines and devices are joined to the domain.

I can access \\datastore\backups from server01.

From TMG01 I get

Error code 0x80070035 The network path was not found

Using both the IP and the hostname.

The Samba logs from the NAS look like this:

Jun 27 13:12:15 DATASTORE smbd[12611]: smbd version 3.0.28a started.
Jun 27 13:12:15 DATASTORE smbd[12611]: Copyright Andrew Tridgell and the Samba Team 1992-2008
Jun 27 13:12:15 DATASTORE smbd[12611]: [2011/06/27 13:12:15, 0] auth/auth_util.c:create_builtin_administrators(792)
Jun 27 13:12:15 DATASTORE smbd[12611]: create_builtin_administrators: Failed to create Administrators
Jun 27 13:12:15 DATASTORE smbd[12611]: [2011/06/27 13:12:15, 0] auth/auth_util.c:create_builtin_users(758)
Jun 27 13:12:15 DATASTORE smbd[12611]: create_builtin_users: Failed to create Users
Jun 27 13:12:15 DATASTORE smbd[12611]: [2011/06/27 13:12:15, 0] auth/auth_util.c:create_builtin_administrators(792)
Jun 27 13:12:15 DATASTORE smbd[12611]: create_builtin_administrators: Failed to create Administrators
Jun 27 13:12:15 DATASTORE smbd[12611]: [2011/06/27 13:12:15, 0] auth/auth_util.c:create_builtin_users(758)
Jun 27 13:12:15 DATASTORE smbd[12611]: create_builtin_users: Failed to create Users
Jun 27 13:12:15 DATASTORE smbd[12611]: [2011/06/27 13:12:15, 1] smbd/sesssetup.c:reply_spnego_kerberos(316)
Jun 27 13:12:15 DATASTORE smbd[12611]: Failed to verify incoming ticket with error NT_STATUS_LOGON_FAILURE!

I have tried removing the NAS from the domain, deleted it from AD, rejoined without any luck.

The NAS must be able to stay on the domain while this is working.

TMG is very locked down by default for localhost traffic (so much so that you can't even RDP into it). If you use the traffic simulator, it will tell you exactly why the traffc is being denied.

You will need to create a new access rule from Local Host to the IP Address of the NAS.