I'm not worried about the 'Other'. I deleted ALL my movies and videos yesterday, and emptied the Trash too, but the image on the left still shows 32gb of movies. Something wrong there. Maybe a reboot and see?
Edit: Omnidiscsweeper is showing the correct figures though
Do you have Time Machine activated? If so, it stores some temporary files on your local drive that can be overwritten if necessary. Finder reports the space free, while Disk Utility reports it as used.