Sorry, it seems I reply a bit too late, because Klauss solved your problem.
As far as radeon free driver is concerned, I'm afraid I think It is simply unable to handle Vegastrike at the moment.
But, I'm able to get through the menu to come to the game (which brilliantly runs with... less than 1 FPS on my dev laptop).
FYI:
- Linux Omicron 2.6.32-gentoo-r7 #3 SMP Sat Jun 5 23:09:28 CEST 2010 i686 Intel(R) Core(TM)2 CPU T5300 @ 1.73GHz GenuineIntel GNU/Linux
x11-drivers/xf86-video-ati 6.13.0
x11-base/xorg-server 1.7.6
media-libs/mesa 7.7.1
x11-libs/libdrm 2.4.18_pre20100211-r1
x11-drivers/radeon-ucode (not installed: r550).
Hope it helps
@Klauss & Chuck: Now that my exams are over, I can get down to business and have a look to the universe generation process.