We just had a similar problem here, the cause of which was a fixed MTU setting in the router.
But that can't be the cause for you, as Fritz!boxes don't have such a setting option, as they support MTU clamping by default.
Or do you have another router between your PC and Fritzbox?