I'm using the latest (2.0.40) NextGen plugin. Everything worked just fine until now. This is the one and only version I've used on my site so far so no legacy issues. When I'm uploading pictures I get a yellow triangle near them for about 5 sec which says 'HTTP error' on mouseover and then they dissappear from the flash uploader and it says in the top right corner that '0 images were uploaded'. The images doesn't show anywhere in the galleries indeed. The interesting thing is that there are some low resolution (10-30KB) pictures which can be uploaded. I have plenty of storage left so this shouldn't be an issue.
No other plugins were updated or activated since NextGen installed (and worked fine).
I did found a ton of topics about similar problems but almost all of them is connected to much older NextGen versions and none of the solutions work for me.