I'd recommend the same, but it's not going to be difficult at all to replace the PSU fan. Actually, it's a whole heck of a lot easier than in a normal system!

Remember Tony, Shuttle's cooling method is to use heat pipes that go back and up to a heatsink on the back of the system, and have a fan blow the air over that (image below). It's really easy to remove/replace that fan (you don't have to touch the heatsink).

I'd definitely pick the PSU fan as the culprit. The PSU in my wife's Shuttle went bad a little faster than I would have hoped. And that's a tiny fan in there that's probably spinning pretty fast.