Can you use SNMP with any other tool like mib browser from that server? The community string could be correct, but SNMP is blocked to the device.
ave you checked for ACL's on the device that might be limiting your ability to run the SNMP session to it?
It might also be worth setting up an ACL on the device if you have access to see if the traffic is actually making it to the device. A permit statement with the log statement on the end will show the connection attempts on the router log. Don't forget an explicit permit statement if you apply this to a live interface or you could find traffic stops flowing.
If ACL's aren't your thing you could setup a class/policy map that just sniffs for SNMP traffic with no action statements on them just to log if you are recieving any.
If something in between is blocking you port specific traceroute probe might hint as to where. As you mention string I'm assuming you are still using version2c of SNMP so read views shouldn't come into it.