Something really weird happened. My Playstation 3 refused to load updates. I retried at least 50 times, but it failed to load measly 24 MiB update from Sony.
A quick Google-search reveals, that plenty of people are suffering from this problem.
In my case the fix was to change wired connection into wireless. I have no idea what the difference is, but for some reason it did the trick.
Getting the updates into PS3 is rather complex as observed from the network traffic. An update is a HTTP-request and the load is split into 4 parallel loads. Example:
GET /tppkg/np/NPEB00874/NPEB00874_T8/0bbab4e7b137739f/EP4350-NPEB00874_00-NETFLIXRIGEL01EU-A0104-V0100-PE.pkg?product=0085&downloadId=be00b7cc&q=2058b9eb8ab5f2492012c6c5b5a73320d1bde7f004d5cb6734fa2ebf322b971e&serverIpAddr=87.248.207.254&downloadType=fm HTTP/1.1
Host: b0.ww.np.dl.playstation.net
Range: bytes=6126400-12252799
I don't understand why they do that. Obviously there is some sort of bug in the 4.41 firmware.
Update 4th July 2013:
Problem still exists in 4.46 firmware. I had major trouble updating, since my PS3 didn't get 100% of the firmware. The error message reads: "An error occurred during the download operation. A connection to the server cannot be established (80710723)".