To try to kind of answer all at once:

I really meant Edit -> Fill, not Fill tool. My bad.

Selection's Feather is set to 0, Anti-aliasing is off.

Edit -> Fill as far as I can see doesn't have a Tolerance setting, but
I guess you misunderstood me because of my mistake.

I haven't tried Clear, but I will.

Thanks all

Nash