I've hit this problem once before, what I ended up doing was asking for another instructor to fly with me for a lesson to audit my performance, and give a different perspective on my flying skills. Found it very helpful, and made me realize that there was an instructor there that suited my style.
There wasn't really a final straw for me... it was a combination of someone spending more time boasting about their flying career than discussing the current situation in the cockpit... coupled with just a few to many "you're doing fine, just keep doing as you have been and you'll get it", when that plainly wasn't the case.
I should also point out that I've flown with some fantastic instructors too, so that helped to give me a point of reference!
Ultimately, you're paying the bills, you can do whatever you want with your money. If you feel you're teaching someone else to be a CFII then you may be wasting some of it.
If your happy with your CFII's instruction, you may want to fly with someone else for a lesson or two just to get another perspective on your training. It is very common for a student to hit a plateau in their progression, sometimes a different perspective may fix whatever is holding your training back. Just because you are flying with a new CFII does not mean that you are getting bad instruction, I know and have flown with brand new CFIs that were really good and I have also seen CFIs with thousands of hours dual that I would never want to get training of any kind from. One of the most important things with choosing a flight instructor is to get someone that you feel comfortable with.
Hey I guess it all depends. I notice your near your stage 3 check. This is a tough time to switch instructors mainly because you are so close to your checkride. Perhaps it would be good to first try sitting talking with your CFI as to what concerns you and maybe try to find a way to overcome the obsticles. However if you find that you are unable to come to a solution then you can start looking into other CFIs. Make sure that you have a meeting with potential instructors first to make sure they are what you are looking for. You may have to review a bit extra since they would be signing you off for the checkride. It might be best to try and work it out so you can finish your rating first since your so close then you get a fresh start for commercial.. However you are the customer so whatever you think is best for you is what you should decide to do. I have had students switch instructors before. I had one student that my teaching style and his learning style just didnt mesh well. No worries though I just recommended an instructor that I thought would work out well for him and he ended up doing well after that. No big deal at all when you need to switch instructors. All instructors should be very professional about a instructor change request. Good luck!