Connect to Ubuntu machine on local network using Screen Sharing, screen doesn't update
Have you tried opening the Screen Sharing app (/System/Library/CoreServices/) and typing in the vnc:// address to the Ubuntu machine?

You can also try changing the Screen Sharing prefs. With the Screen Sharing app open, go to Screen Sharing -> Preferences and changing settings to the ones that say faster?

Hope this helps.