What's odd is that those apps work on both 3G and on other wifi networks. That should mean there's a problem with the router somehow, but every other device (PC, laptop, another Android phone) works fine. This has also been a persistent problem so the router doesn't just need a reboot.
I used to run a custom ROM so there's a chance something got messed up when flashing updates, but I eventually did a factory reset and returned to stock. And I've tried clearing the system apps' caches of course. Any ideas?