Hello guys,
I had the exact same problem with my Samsung Galaxy S4 and DIR-655 (A4 revision, 1.32 firmware). Installing the latest firmware 1.37 completely fixed the issue. The release notes for this firmware version (released in 6/11/2013) says "Improved compatibility issue with Samsung Galaxy S4". I knew my problem was solved when I saw that statement.
You can find the firmware download from dlink's site using the following steps. First connect your laptop using an Ethernet cable to your router. I read somewhere that it is better to have a wired connection while updating the firmware. Maybe you really don't need it. I don't know; I used a wired connection for this operation. Then, simply type DIR-655 in Google, choose the first link which has to be dlink.com. In the middle of the page, there is a "Downloads" tab. Click that and then click the link "Go to the DIR-655 support page". Then type "DIR-655" (without quotes) in the search box that appears. The search results should list DIR-655 Xtreme N Wireless Router. Choose that. Then from the drop-down for the hardware revision, choose "A" (or whatever is correct for *your* modem; the revision number and firmware number is at the back of the router). Finally, you are presented with the download for the firmware (make sure it lists 1.37 or more). Hitting the download button downloads it as a .zip file. Unzip it to extract the lone .bin file inside it. Then go to the router's admin page (it is 192.168.0.1 unless you have changed it). Log in using admin password (it is empty unless you have set it). Then click the "Tools" tab. Then the "Firmware" tab. You should see buttons to choose a file on disk and to actually upload it to the router for installation. Pretty straight forward from here. BUT WAIT!!!!. Uploading this firware version wipes all your existing settings. Which meant that I had to reset the Wifi password again, etc. If you reset it to the same password it was before the wipe, you don't have to re-enter a new password into all your mobile device in your home. This was a minor hassle compared to the joy of getting my router back in action. One more thing, on the Firmware page that allows you to upload the .bin file, there is a "Check Now" button. I assumed it would smart to actually detect that my firmware was old and download the new one. But no such luck. It just said that the firmware was up to date. Liar! Just use the manual upload path explained above.
I owe a thanks to this forum for fixing my problem. Hopefully, my detailed notes help others. Best of luck!