First, don't set all your bools to false at the start of handleKeys(). That defeats the purpose of checking to see if they were released. I'm really surprised you're not getting the opposite problem. The way the code is written there I'd expect your guy to only move on the frame when the key was initially pressed.
Can you confirm that SDL_KEYUP messages are being generated when a key is released?