Need help with replacing nozzle  

Need help with replacing nozzle

I have a preassembled prusa i3 mk3, and it's been working flawlessly since I got it. But about a week ago I started seeing lots of failed prints, with symptoms that suggested the nozzle was clogged. (Extruder clicking, underextrustion, etc). I wasn't able to get any needles through the nozzle, so I figured it's a good time to replace it.

I followed the instructions for nozzle replacement here and used a bog-standard 0.4mm replacement nozzle from Amazon. But I'm running into problems:

1) My heating block and nozzle are somewhat gummed up with melted plastic, from previous failed prints, so it's a bit hard to see what I'm doing.

2) When I try to screw in the replacement nozzle, it will only screw in about half way (See this pic), then it becomes very difficult to turn, and I'm worried that I'll crack the heating block with my pliers or something.

3) Whenever I try to screw in the new nozzle, the printer will start screaming like a banshee (continuous, max-volume beep), and the message "Err: MAXTEMP" appears on the screen. As far as I can tell, I haven't destroyed my thermistor or anything, but how can I be sure?

Do I need to tap the nozzle hole with an M6 tap? Do I need to replace my heating block? If so, how do I do that? What parts do I need?