I talked them into it. They ran hardware tests and found nothing
wrong. Then they started to blame Ubuntu so I reminded them that my
wife's computer which is virtually identical to mine runs Ubuntu
perfectly. Except her machine has a 500 watt PSU.

So now I have a 600 watt PSU. The first time I got the computer home I
had to hold down the shift key while booting (only the first time).
It's been running fine since then. Here's hoping.