Just a fast note.
After reading the above, I started doing some more research, and started to see more info about the potential speed problem. So I went into my BIOS with the intention to reset my speed back to 1333Mhz.
That's when I noticed that I've been lying. I *THOUGHT* I'd upgraded the BIOS when I built the system, but apparently I didn't. There it was, plain as day, telling me that I was using v2001 of the BIOS, when all along I thought I was using v2105.
So, I went ahead and upgraded from v2001 to v2105, and after doing so, I made sure the memory speed was set to 1333Mhz.
At which point, I booted into XP and Win7 just to double check they were still working (they were), and then tried again to install Ubuntu 9.04 (x64)
This time it went PERFECTLY!
Not one single glitch or weirdness. I've been running 9.04 for a few mins, and done a full update of all packages. So far, it feels rock solid. Not even the smallest hint of instability. In addition, I've just now added Xunbuntu-Desktop with Synaptic, and still no hint of weirdness.
So, I'm sorry to admit that I've been lying all along. I *THOUGHT* I'd upgraded to the latest BIOS, but I had not.
At this moment I don't know if the solution was upgrading the BIOS, or dropping back to 1333Mhz. But one way or the other, my system appears to be 100% stable and working great with Ubuntu 9.04 (x64)
Thanks for all the help and comments posted by everyone. And I truly hope this thread will be useful to the next person with the same problems on an ASUS M4A78T-E mobo.