@Xallis : Do you have this problem in windowed mode as well? It isn't clear from your original post if the problem is only related to fullscreen mode or if it's actually related to the resolution your desktop is set to.
If you're having trouble starting the game or connecting to a server while in widescreen resolutions, even in windowed mode, then it sounds like a broken installation. Maybe
my linux install guide has a hint that might help?
@kai4785 : That looks nice. Is it primarily intended to lower the complexity/barrier of entry to running EQ on linux, or is it more of a convenience tool for switching into fullscreen, isolating to a single core, etc?