Are you sure you're loading the XFree86-VidModeExtension X extension? You can check with xdpyinfo
-- the last few screens of lines are info on visuals, and just before that is the list of loaded extensions. If you don't see XFree86-VidModeExtension listed there, then you don't have it loaded.
I'm not quite sure how to load it, but I think it has something to do with the SubSection "extmod" in your Section "Modules" in your XF86Config(-4) file. But check to see if it's loaded before trying to get it to load, obviously.