Sounds like you're doing everything right. Try these things:
First, reboot the router.
Second, make sure you don't have it set to only allow devices with specific MAC addresses. If so, either turn that off or enter your phone's MAC address into the allowed list.
If neither of those help, check your router's firmware to see if there's an update available. If so, get it, as these updates fix all sorts of bugs. If you've never updated a router's firmware and don't feel comfortable doing it, get someone to help you, since you don't want to brick it. It really isn't too hard if you follow the directions.