Easily. The only real requisite is to have hardware. It’s like dying, the only real requisite is to be alive :).
Now, a couple months ago I assembled a new system and I couldn’t make the onboard video work. It would go nicely until X kicked in, and then fail, regardless of acpi/apm/etc settings at boot. I don’t recall if it went to level 3, froze or rebooted. There was no problem with windows XP, however.
Fortunately the shop I buy from is quite accommodating. We tested another mobo of the same model they had there (just to rule out a defective mobo) with various live-CDs and got same result, so they gave me another mobo (an Asus this time). During the test one of the tries with the Partition Magic live-CD did work, but then didn’t any more, and that was a sign of instability.
What I more or less concluded is that particular mobo implementation wasn’t compatible with linux/X/whatever, just that.
I don’t think this is your case, because of the memtest failure (which worked ok in the defective mobo), but it is an example of how new, shiny, modern hardware may fail.
The memtest program is usually a trimmed-down version of free-DOS and the test program. It only access memory and the video buffer (a very old and simple bottom-line video mode supported by all cards).
Even if a system always worked OK with windows it may fail the test, as linux tend to use all memory available, unlike windows.
If your computer reboots on starting the test I’d say that there is something very wrong with it. It has nothing to do with linux per se, as at the time of the test there’s no linux kernel running on your computer.
However, I doubt it is really the memory, unless the problem is at the very start of it, where the program tries to load itself. The only thing I can think of is trying to swap the memory or try another.