Could you give a litte more information?
What are your specs, e.g. CPU, RAM, GPU?
What version of Ubuntu?
What video driver are you using?
What version of Mupen64Plus are you using?
How did you install Mupen64Plus?
With which video plugin?
Are all games affected?
You also said you tried Project64, which only works under Wine (astonishingly well). You did try the native Linux version of Mupen64Plus first, right?