Well - I'm having mixed results here (some are bad, some are dreadful).
When I first went in to Powerstore Admin and added a new product, I used your image and it uploaded ok. I tootled off to check other stuff, and came back just to re-test.
Now when I try to create a new product and upload an image (any one) the 'Please enter a valid file (.gif, .jpg, .jpeg, .png).' error displays.
When I click 'cancel' I can leave the page. When I click 'New Product' the page opens with any info I entered the last time still there, plus the error messages.
I exit the PCMS pages all together, clear my browser cache, close and open the Browser again and go back to Admin to try to add a new product. The old page comes back with the old info and the 'valid file' error messages.
So as far as that goes, I am now in the same boat as you!
However, - and it may be the same for you - if I go to a 'Products' and then choose to update a product that has already been added, I can use any images from my machine, including the one you posted.
So it's not a permissions issue (I believe). Images can be uploaded from the Update Page, but (apparently*) not from the Insert page.
NOW*: I went to check in my Images/Upload directory using my FTP programme, and there are now a dozen of so copies of your file (names changed with incremental value) and a couple of dozen random images I tried from my machine, all of which the image upload error message in the Insert new item page said were invalid file types.
SO: The images ARE uploading, BUT for some reason, the validation on the file field id is failing when it shouldn't.
I have no idea what causes this, but the problem seems to be just a tiny glitch with validation that turns in to a huge problem with functionality.
I will do some poking about this evening (and after that I'll have another look at this problem) and let you know if I find anything out.
I don't have any real-life products in the database yet, so will clear all values from phpMyAdmin then start afresh to find out exactly when the error appears. I will need to do that anyway, as I can't get a 'clean' add-a-product page to test with.
In the mean time, hopefully this info will be useful to any WA_guy who feels it would be nice to spend his Sunday looking at problems concerning WA_stuff.
After Tea Update: Not sure if it helps, but when I remove both the thumb and image validation code from the insert page, the images upload with out a problem. I currently have a baby for sale for $9.00.
The more I go on, the greater the paranoia that I might be missing some obvious setting, or some step in the guide. Have a cople of things to try, yet. All a bit academic this, 'cause Jason will pop back in tomorrow and post, "Change (this) to (that)", and that'll be it.