Make sure that you aren't using too much cubelube. I found that if I over-lube my cube... it starts to get 'gummy'. It feels like things are starting to stick...
The tutorial for PuzzleProz on lubing is GREAT. Take out an edge, flip it so that the 'opening' is facing up, fill it 1/2 way (or a little less), and place your cube ONTO the lube-filled edge.
This ensures that you aren't squirting in tons of lube (with their shotgun style syringe), and it allows you to IMMEDIATELY start rotating the cube faces to get the lube worked in.
I usually lube my cube 30-45 minutes before I go to bed. I will work the lube in, and then set it on a paper towel, so that any 'excess' lube won't get all over, and the next morning my cube is perfect. Before I started doing this, I was lubing every 2 weeks, and I'm now at 1 month w/o needing to re-lube.
Make sure that you are cleaning it too. I was SHOCKED at how much crap there was inside my cube after ~2 months of use. I know that I'm not that fast... but I know that my 'slow times' are based on the need to practice proper technique, not limitations of my cube.