We are finally able to reproduce the intermittent lag spike problems in-house. What it required was a more social developer (Facebook, email push, push notifications, etc.) whose device would encounter these problems over 3G or Wifi for us to be able to track it down.
We compared devices, ran a few tests, and determined that any one of the following could interrupt your network connection to Pocket Legends thereby affecting game play:
1) Email push enabled
2) Push notifications enabled
3) Other applications that require network access (eg. internet music streaming)
4) Other applications running simultaneously
5) Poor network connection
6) Incorrectly configured router if playing over Wifi
With 1-4 disabled, there were no lag spikes when playing on the devices that had them previously, 3G or Wifi.
Pocket Legends requires a constant, stable internet connection. If your device is doing anything other than playing Pocket Legends (and it may be doing other things based on how you have configured other applications), you may encounter what appears to be slow performance, or high ping.