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?
Well, thats the problem. I don't think SDL_KEYUP is working because when I press the key the player starts moving, but when I let go of it the player is still moving. I need to be able to determine when the key is released so I can stop the player.