I had simillar problem once. In my darkroom beginnig times I once filled fixer bottle with water because I wanted to wash it later, and totally forget about it. So, when making prints I regulary developed it, stop, but fixing print with water instead of fixer. It took me 10 prints and 2 times fresh developer mixing untill released it was fixer error
As Ole said, it is most probably fixer problem. When you said your fixer is brand new, is that means you bought new fixer, or you have old fixer bottle, but fresh working solution made? If fixer is too old, buy new one. Check if your fixer working solution is week, that is if fixer is too much diluted, or fixing time is too short. For example if fixer can be dillued 1:9 to 1:14, dilute it 1:9. And if for 1:9 dilution is needed 30 seconds fixing, leave print in fixer for 1 minute. And move print or rock the fixing tray if not continuisly, then from time to time during fixing. Next is working temperature checking, but I think temperature is not problem, for example if you work under room temperature, and if your fixing solution has room temperature, let say between 18(20 is better) and 24 degrees Celsious, you shouldn't have problems... And if you want, buy new fixer, that will make things easier than finding out what is wrong with your existing fixer And if with new fixer you still have same problems, then it is not fixer, but again, it is most probably fixer problem.
Next, you can use water as stop bath, that is not to use your vinegar/lemon stop bath, but to use plain tap water as stop bath. That way you can eliminate stop bath mix as cause of problems during testing, even if stop bath probably is not cause of problems.
Oh, I am sorry for asking, you wash print after fixing it as you should, that is sufficient time of washing at temperature let say close to processing temperature