How to access Windows Server 2008 R2 file shares from a different subnet

We have a couple of severs that used to be Windows Server 2003 that we recently upgraded to Windows Server 2008 R2. A couple of details to set the situation up:

• We wiped the OS and re-installed.
• These servers are on one subnet (172.16.x.x) and we are trying to access some file shares on them from another subnet (10.34.x.x).
• Firewall is disabled on these servers.
• Trying to access with UNC "\\172.16.x.x\sharename" and net use \\172.16.x.x

However, we're having problems doing this. We are getting "The network path was not found".

Here's some of the things we've tried so far and the result:

• Tried accessing the share from other (non-2008) servers on the same subnet… Success!
• Ping servers from different subnet… Success!
• Telnet connection into port 139 from different subnet… Success!
• Took a scan through Local Security Policies to see if something obvious needed to be enabled / disabled / configured… Fail

I'm not sure where to look next. I know that the router between the two subnets is locked down pretty good, but this did work for our 2003 servers. Has anything changed in the way of ports used for UNC / file share access in 2008? Maybe I'm missing some security policy setting?

Hoping somebody can take pity on a poor programming guy that can't figure out something really simple. 🙂

Thanks!