Slow Network

root@ogma /root]# ping 192.168.16.1
PING 192.168.16.1 (192.168.16.1): 56 octets data
64 octets from 192.168.16.1: icmp_seq=0 ttl=254 time=2797.0 ms
wrong data byte #0 should be 0x3f but was 0x3d3d 51 b4 3c 9b b c 0
8 9 a b c d e f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 24 25 26 27
28 29 2a 2b 2c 2d 2e 2f
64 octets from 192.168.16.1: icmp_seq=1 ttl=254 time=3167.2 ms
wrong data byte #0 should be 0x41 but was 0x3e3e 51 b4 3c 76 1 c 0
8 9 a b c d e f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 24 25 26 27
28 29 2a 2b 2c 2d 2e 2f
64 octets from 192.168.16.1: icmp_seq=2 ttl=254 time=3037.2 ms
wrong data byte #0 should be 0x42 but was 0x3f3f 51 b4 3c 76 1 c 0
8 9 a b c d e f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 24 25 26 27
28 29 2a 2b 2c 2d 2e 2f

--- 192.168.16.1 ping statistics ---
6 packets transmitted, 3 packets received, 50% packet loss
round-trip min/avg/max = 2797.0/3000.4/3167.2 ms

They have a Cisco 1600R router. We have a Cisco 2500 router. I am pinging the internal interface on their router, although it still happens if I ping their external interface as well.

This happens intermittantly, and clears up on its own. But, while it's happening, their connection crawls.

I've talked to our frame relay vendor, and they can't find anything wrong with the circuit. Any ideas? I can't find any decent explanation anywhere. For 1000 points...a explanation AND more importantly, a solution would be great!

Thanks,

Christian