Students change advisors all the time for all sorts of reasons. While it is important that advisors and advisees have to recognize that they are supposed to work on improving their relationships and fight through tension, sometimes it just doesn't work out or will not work out in the long term. I've changed advisors and during that process, I found several other students who have gone through the same experience.
It is important to recognize that this does happen for better or for worse and it is important for you to do what is necessary to do what is best for you. Despite what you would think, people (even academics) don't really put much weight on seeing someone change careers or direction so you shouldn't worry about such things being regarded as suspicious.
The first step would be to find a set of people that you can rely on for rational advice since this will likely be an emotional transition. Parents and close friends come to mind but also finding an older student, administrative staff, and understanding professors will be key. In my case, my co-advisor and one of my committee members were resources in addition to several senior graduate students who had changed advisors.
The second would be to start to find a new advisor. If you get along with your current advisor, he would make good suggestions, if you're switching behind his back, probably not so much. As you a mid-PhD student, you now have a much better understanding of what type of advisor/mentee relationship you want and you can narrow down advisors based on that reputation. During my search, I got in touch with senior students first asking them able advising styles (and availability of funding). Only after that initial conversation did I meet with the advisor themselves. Despite what you would think, advisors actually like picking up/stealing veteran graduate students from other advisors due to the expertise that they may add to the discussion.
Finally is the administrative side. You chair will have to know about this and your committee will likely be restructured. People don't have to know the reason why you've changed (my current advisor still doesn't know). If possible, try not to burn any bridges since you will likely need his (his/her for other people reading this) signature at somepoint on your thesis. Try to keep things professional since this really is a career based move rather than something personal although it really is.
The best news is that everyone I've known who have changed advisors are/were really happy about their new sitatuion. It's just a very stressful transition but it really wasn't as stressful as I was expecting.
(edit) I've noticed this about eykanal's answer regarding the timing. Yes, it is inevitably that you will lose some time especially if you're in the thesis writing stage of your career. However, if you're an earlier student in the dissertation/research phase (I was in my 3rd year), I didn't feel like I lost much time. Most of the first years of grad school are "wasted" relearning learning and taking classes. Especially in the sciences, most of the early years is developing various soft-skills and competence which isn't lost when you change advisors/research projects. Furthermore, spending an extra year to reconfigure a PhD is probably better than falling into ABD purgatory.