Can't replace image in header

Hi everyone,
I am trying to replace header image but it does not work for some reason (I’m editing style.css file). I’ve done it before successfully, but not this time.
The theme I’m trying to edit is Three Column Blue. I’ve tried some other themes with the same result.

I tried to replace the image with the same size and same file name, but as soon as I upload my replacement image it does not show at all.

Ideally I’d like to change the dimensions as well, but for now I have to figure out why I can’t change the image even with the same dimensions/file name/location.

I can edit everything else though.
I’d appreciate your input very much!