Realizing no one at my school does quite what I want to do In short: I'm three years into my Ph.D. program, have learned some things about what I seem to be good at and what not so much, and have realized I don't have as much in common with my advisor's research goals as I thought. We talked about me switching advisors, but discovered that anyone else at the university is an even worse match. I'm now facing the question of whether to:

Do what I'm good at, but with not much guidance from my advisor;
Do what my advisor works on, although this has not been very productive so far;
Switch universities, despite having 3 years getting to know my current institution.

Probably relevant is that my field often has very small groups; I'm currently my advisor's only student and had basically been working with just him. So I am not abandoning a large group project.
In slightly more detail: halfway through my first year I began working with my advisor, on a sort of toy project to 'test me out', I think. He does computational work and wanted to apply a new algorithm to a particular set of problems. My background is also heavily computational, so I could understand the algorithm very well, but I do not know much at all about the problems we were trying to apply it to. This became a continual sticking point. We worked on this for about a year and a half, and it turned out to be quite a bit trickier and slower than we thought. We never got any results, although often feeling like we were &quot;just a few issues away&quot;. On my own, I was continuing to learn things about algorithmic problems in our field and wrote them up as notes.
Last summer I showed a couple of these notes to my advisor, and he said they might be interesting, but he didn't know much about those topics at all and couldn't give much feedback. He said -- quite reasonably -- that I should focus on our main project, as I should have real work to present by the end of my third year (roughly, this coming May, so maybe 9 months after he said this). I tried sending the notes to a couple of other contacts I had who would know about it, but they were both too busy to read them. I put them on the shelf.
Over winter break I chatted about my notes with a friend-of-a-friend who has a hobbyist's interest in the field, and he suggested just emailing the notes to a 'big name' in the field. Reluctantly I tried this with the first note and was quite surprised when the 'big name' got back with positive feedback encouraging me to publish. I uploaded the first note to arxiv and got good feedback via email. Upon this further encouragement, I spoke to my advisor and said I would like to pursue this type of work further. He agreed that we've been doing so well has not worked out well and that perhaps we should change projects, or maybe I look for a new advisor at my institution.
We've basically dropped the 1.5-year project, and are switching to a much simpler shorter problem to prove the algorithm. It will be a much less interesting thing in the end, but we want something to write given the work we've done. We looked around the university and found no one who actually knows anything about what I've written about. This is disappointing because it's a topic I want to pursue. There are other universities I could go to with people much more interested in my work. My second paper is almost done now, it resolves a well-studied open problem in the same subfield (so is generally something people are excited about), and is again something no one at my institution knows anything about. I'm quite lost on what to do moving forward.
Seek an external co-advisor who can give you the guidance you need.
A co-advising arrangement can be a win-win situation: your advisor would still have you as a graduated student under his belt, the co-advisor gets to be a co-author of the resulting papers, and you don't have to seek a new position and deal with the complexities of moving and changing your living circumstances halfway during your Ph.D.
Candidates for being a co-advisor are researchers that are enthusiastic about the research problem and possess the required expertise. Examples would be the &quot;big name&quot; researcher and some of the other people who gave you feedback.