This is just a guess from past posts. Go to edit/preference/general at the top click image interpolation and in dropdown box click "nearest neighbor".
Can you post before and after examples? Small crops will be fine.
Are you looking at the image at 100% zoom? You need to be.
Threshold will have made pure black and white pixels, but some pixels will be semi-transparent because the Quick Selection made a soft edge.
Do 'Layer > Layer Mask > From Transparency' then apply Threshold to the mask to give it a hard edge, too.
Ah! So that was the problem! I thought it went bezerk or something.