Can you please try deleting the Wireless profile for this specific network? Here you can refer to the Wireless profiles:
I had never used the Profile Manager, I didn't know that it exists. I did simply use the standard W8.1 Wlan tool.
In the Profile Manager, I found that I had a second profile for the Fritzbox, which had the original SSID, and I guess also the original password that came with the box.
It was on top of the profile with my current SSID.
Could it be that the Profile Manager tried to connect to the Fritzbox with the first profile, maybe because he identified the MAC address, but couldn't connect because I has changed the password and SSID changed in the meantime?
I have unfortunatelly tonight no time to connect my laptop to another network to check if it can reconnect to my homenetwork afterwards, but I'll let you know asap if the issue is gone.
Thanks for the hint!