Ah. I've only just noticed that the original poster is in Europe. Check what WiFi channel your router is using. The US only allows channels 1 to 11 but other regions like Europe allow 1 to 13. If the Kindle isn't correctly designed by Amazon to set the Europe region if you're in Europe then it won't see your WiFi access point if you're using channel 12 or 13.
Rebooting or altering the settings on the router is making it restart and rechoose a channel if it is in automatic channel mode.
I've noticed several US designed/made devices which just assume that you're in the US and don't allow you to change the channel allocations. In these cases, you should change the channel on your WiFi access point and fix it at 1, 6 or 11 since they're the generally non overlapping channels.