Mari0 running really slowly

[Sky]

The disclaimer: I'm running Ubuntu.
The problem: Mari0 runs just fine in the mappack Super Mario Bros. (except for a few frameskips). If I play a mappack with a tileset, the game lags horridly - the larger it is, the worse it is.
The complications: Running Mari0.exe in Wine works fine (but I can't find a way to use mappacks...). Ortho Robot works just fine. Playing Bejeweled in my browser does not.
Specifications:
OS: Ubuntu 12.04
Laptop: Toshiba Satellite C655-S5225
CPU: Intel Pentium 4 (with integrated GPU)
Other notes: I've tried finding a driver for the GPU. It actually worked really well when I finally found one - until I turned my computer off; it didn't work after that.
(Sorry if I'm missing anything/doing this wrong; I haven't done this before.)
Thank you for your time.

[Sašo]

Perhaps check the BIOS settings if GPU memory can be set to static - from what I've seen right now it's dynamically allocated and who knows all what that does.

Also additionally, you could try this: http://intellinuxgraphics.org