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=18.104.22.168&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)".