I also ran into this problem saulnierpr, using almost identical logic to yours. I have a solution that might work for me, because of the way I performed my implementation, but it involves only looking at every 1 of X permutations and so results in a smaller amount of permutations for the program to analyze. Currently, once my program has all the valid words, it chooses one at random and plays it. Because I already have this element of randomization, I feel like I could get away with looking at 1 of every X available permutations. However, the flaw with doing this is that there is a chance that the program will skip all the permutations that ARE valid words won't find any permutations that actually work, even if in actuality there are 10 or 20 that would..
On another train of thought, maybe it would be possible to look at each permutation and filter it out of the program if it didn't contain at least 1 vowel and 1 consonant. By the basic logic of the program, you have thousands of permutations to go through, but each one also has to go through thousands of entries in the word list looking for any match to a word. If you could filter out entries from ever even reaching the part of the loop where you compare them to the word list, you might be able to save time.
In summary, I think the solution to this problem involves figuring out a way to avoid looking at some of the entries and/or figuring out a way to avoid having to compare every possible permutation to the word list. Try to think back to the logic of the third problem of problem set 1 :) I hope this was helpful!