That error response is one that I constantly see, however its usually comes up when either something is blocking the actual packets from getting through to the remote host. I would ask if it were possibly caused by sending an oid to the remote device that required a RW string and only a RO was configured, but I *think* that would produce a different
error response.
Have you tried running each of the snmp commands individually against the remote host to see if you can find one in particular that times out against it, or if its the host in general?
humbly -c