I figured out what was going on here. Turns out the twofishes geocoder was running out of memory on an AWS m3.medium. I added 4GB of swap and rebooted and it worked.
It's worth mentioning that simply restarting the twofishes service was not sufficient, I needed to reboot the machine. After that, postal code queries started working again.