First, and most important, I think you're mixing up "actual" and "equivalent" RAM speeds. (That, or you've just worded things oddly.) DDR(2,3) RAM is called such because it performs a read, a write, or whatever, twice per clock cycle, essentially doubling it's actual clock rate. DDR1 RAM, like you have, usually ranges from 100 MHz to 200 MHz in actual clock rate, which amounts to an effective speed of 200-400MHz. CPU-Z shows effective clock speed in all circumstances.
The RAM in your system will 1. all run at the same speed, and 2. run at the lowest supported speed by any one stick of installed RAM. Different sticks of RAM can't run at different speeds in the same system.
Therefore, I believe you might've misread your CPU-Z output, and were instead looking at each stick's capable maximum, rather than it's current running speed.
In the above screenshot from my workstation, I have my DDR2 RAM running at 266 MHz (533 effective).
Your machine is, because of your one 133MHz stick, likely running at 133 MHz, or 266 MHz effective, because of your 256 MB stick. If you were to replace that with a shiny new 200 MHz effective stick, that would then boost your effective RAM clock speed from 133 MHz right now to 200 MHz, or 400 MHz effective.
As far as running RAM faster than your FSB is concerned, this isn't an issue with modern processors. In particular, your AMD HyperTransport-based (you don't have a "FSB") processor has an on-die memory controller, which allows you to run your RAM at any speed you like over or under the FSB speed without issue. Intel-based processors that use a FSB (pre-i5/i7) see some gains from running their RAM at the same speed as their FSB (this is called 1:1 operation), but they're still very minimal. FSB-based processors might not like RAM running slower than the FSB, but faster works fine.
The only things that could affect whether or not that stick of RAM would work are memory timings and DIMM voltage. For the former, memory timings will likely be adjusted to the lower of your two sticks of RAM, just like the frequency. Voltage probably won't be be an issue, as usually only goofy overclocker's RAM needs higher voltages than normal.
Finally, in regards to whether more headroom or more speed is important -- well, you get both more speed and more headroom, in this situation, but in general more headroom is the more desirable trait. RAM speed often has very little effect on modern applications, and a doubling of memory speed never equates to even a 25% boost in performance for most real-world tasks.
So, in short: Yes, you can run that 1GB 400MHz stick fine. You already have a 512MB 400MHz stick in there. Your system'll get a tinge quicker, and you'll have more working space to Get Stuff Done in.
Best Answer
Problem solved!
After a lot of searching, I found this walkthrough Although it's for a different model, physically it's identical to my Satellite 1900-603.
It turns out the second memory slot is under the keyboard - NOTHING I read before (including the manual) suggested this. Also, it turned out each slot originally came with 256Mb of memory installed which explains why, after I installed one 512Mb stick, Windows reported 768Mb of memory.
Anyway, after wrestling the plastic strip off and getting to the keyboard (Tip: try and shift the strip to the left a little first which releases the plastic 'teeth'), I've now installed the second stick and Windows shows 1Gb RAM is now installed.