Honestly, if I was in the position of having to re-take the GRE's, I would most certainly do it before the August implementation of the new GREs. Yes, analogies and such are going to be gone...but, on the other hand, the math section is going to be more challenging, and the changes in the verbal are going to be even worse. Fill-in the blank is going to be even more treacherous, with three blanks to fill-in, with each blank, getting an option of three words to choose from....so its essentially multiple, multiple, multiple choice-fill in. This is a disaster. As someone who took a KAPLAN course very recently to study for the GREs, KAPLAN is recommending that people take the current GRE test, because the changes that will be implemented in the new one are going to be....well....making the test more challenging in many ways.
My guess is that most test-prep companies have a good system worked out that has been in operation for a number of years to help study for the current GRE. In terms of prepping for the new one....I'm sure they are still trying to work those kinks out, and thus could provide a less-than satisfying experience for you when you study for it. Personally, I would definitely take it before August. I looked at how the new test is going to be....and, IMHO, the current GRE is more approachable and manageable.
With that said, I don't know the exact difficulty that you are having in terms of the verbal section. However, the majority of problems that arise when dealing with the verbal GRE is a limited vocabulary. Much of the GRE is concerned with how well you know the meanings of words, and how these words are used. Therefore, having a good handle on vocab alone should boost you by 25-50 more points on the GRE. The best thing that I found, was to buy (its like...20 bucks or something) the GRE 'VOCAB IN A BOX' which is a 500-word vocab flashcard package that KAPLAN puts out. These words are commonly found on the GRE. Just from taking my GRE two months ago, a good chunk of the words that I came across were in that box. So, I would look into that very seriously.
I took PR initially, but I had to stop it because I got sick, and couldn't attend classes. When I got better, I took another class w/ KAPLAN, and personally, I loved KAPLAN. I love their structure, and I love the fact that they teach strategies that actually work. I boosted my score from an initial 1000 practice GRE score to 1350 (official GRE score) in three and a half weeks of studying, while still being very very sick. BTW, I took the KAPLAN course on-line. So, there you have it. My two cents. Good luck!
By the way....the app that symphonyinc mentioned is awesome, and really worthwhile. Go for a walk, and flip through some vocab words. Traveling in the car, flip through the vocab words. At a movie theater watching the previews, flip through some vocab words. At church...flip through some vocab words....you get the picture.