I have the same issue, also running Linux Mint 13 KDE. I'm new to Linux (2 weeks now).
When I'm only on a single monitor, fullscreen works fine, filling up the entire screen size.
Only when I'm using dual monitor display does the fullscreen video remain small. The problem is not only in Youtube. I have tried several other Flash-based online video players, and each one messes up in a different way when I go fullscreen. For example, vimeo fullscreens on the wrong monitor (in my case, the smaller one). In Novamov, it only shows half of the video. Some work fine (you mentioned Hulu). The problem occurs in both Firefox and Chromium.
First, I tried updating the flash plugin, then I tried the Flash-Aid add-on for Firefox, but it didn't change anything.
Then, I tried loading the proprietary drivers for my video card (ATI Radeon HD 5450). In the Catalyst Control Center GUI (with admin priviledges), I could select "Single display desktop (multiple desktops)" When I restarted the computer, fullscreen worked perfect for all flash video players. The problem was that now my 2 monitors were separate desktops, so I couldn't drag windows from one to another. Catalyst has a feature called Xinerama, which supposedly allows dragging windows across screens. I selected this and restarted my computer, and while I could drag windows between monitors, my Youtube problem returned.
That's the closest I could get to solving this issue.
Does anyone else have any ideas?