The description of The Stuff of Nightmares implies an immunity to fatigue causing critical effects, unless done by psychic/holy means, does this extend to regular fatigue? Why or why not?

Per the wording, it's not so much an immunity to fatigue , as it is the critical effect that would normally cause fatigue is ignored.

Fatigue from a non-critical effect would not be affected by Stuff of Nightmares. That said, anything with Stuff of Nightmares probably also has a high Toughness Bonus.

Here's an analogy: paintballs don't break open when they hit you (because magic) - you're immune to getting covered in paint by paintballs, but if somebody dumps a can of paint on you, you're still covered in paint.