Welcome to LMR. I would recommend an Arduino -- it is easy to program, with lots of code examples and a large user community. The Adafruit forums are welcoming of new Arduino tinkerers (http://www.adafruit.com and http://forums.adafruit.com). There are some "motor shields" to get you started (so you don't have to build your own circuit boards until you're ready).
An Arduino/"Start Here" bot may be cheaper than a "BOE Bot", but you may want to compare. After you are done buying servos and wheels and such, it may be more expensive to use an Arduino. I've never priced the difference, so shop around. The "Start Here" bot may be a good bet, and you can probably substitute an Arduino and Motor Shield for the PicAXE http://letsmakerobots.com/start
Arduino it is then, I'm thinking of using the Arduino with lego mindstorms rcx parts, because that is stuff I already have and I have a really small budget. I might even take apart the rcx brick and stick the arduino in it :)
Mindstorm sounds fun to integrate. I've seen screenshots from their GUI programming software and it reminds me of LabVIEW. Since it uses I2C, serial devices, digital I/O pins, et cetera it looks like a good match.
Also I found this: http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1253126972
If you make something interesting, take some pictures and post it as a blog entry! (http://letsmakerobots.com/node/add)