I run a Linksys WRT54g with Tomato firmware. Early on, I had a brief time where my GS4 also showed saved, secured but wouldn't connect. I believe this was the morning after I got the GS4 and had already established a wifi connection the night before. I piddled with it for a few minutes... and honestly don't recall what I did, but it finally connected and I've had no trouble since.
Sorry, I know that's no help. But I did think that an odd problem but since it only occurred once and has been rock solid since, I haven't thought much about it.
I'm curious what you find when you get the issue resolved.
FWIW, I set a static IP from within the router firmware. But it also connects just fine via DHCP in other wifi environments.