Thanks for the response.
I have some evidence against an issue in the backup procedure (though I'm not ruling it out). We moved back to taking the backup off of the primary and all errors for all three clusters went away. All of the hardware is the same, OS and postgres versions are largely the same (9.2.3 vs. 9.2.4 in some cases, various patch levels of Cent 6.3 for the OS). The backup code is exactly the same, just pointed at a different set of boxes.
Currently I'm just running for a couple of days to ensure that we have viable static backups. After that I'll redo one of the restores from a suspected backup and will post the logs.
-David