Have you tried reinstalling your graphic card driver?
Yes, it's mentioned in my startpost.

I've managed to solve the issue by myself.

First of all, I discovered that uninstalling my "compiled" SDL versions (1.2 and 1.3) made some games (like extremetux-racer) work again. They would be using the SDL shared objects that were provided with ubuntu (in /usr/lib).

After some more searching, I found out that when running ./configure in my SDL1.2 directory, the following line would show up:

checking for OpenGL (GLX) support... no
So, I opened configure.in to see the reason. I found out that GL/glu.h could not be found.
Thanks to apt-file, I found out that the GL/glu.h was part of the libglu1-mesa-dev package, which I installed.
After running ./configure; make; sudo make install; openGL support was detected and everything WORKED again!

The issue was that the original error message pointed me in the wrong direction. It took me several hours before I started blaming my compiled SDL library.