Are you sure the phone was rebooted? I had a similar problem yesterday with my phone. I had entered the network password incorrectly and couldn’t get my phone to let it go and enter the correct password. I did a reboot by holding both the menu and power button until it shut down.

Another thought, is there a chance that the phone has been connected to another network with the same SSID as the main network?