The entire CMU robotics club uses those wheels, they are really nice.
As for velcro use, I *strongly* encourage it for really small robots like this one. For larger robots, only use it for batteries.
I'll link this to the $50 Robot mechanical page now as an alternative construction method.