When to look for a new PhD position?
While this problem is very personal I can offer a bit of guidance rather than an answer to your problem. You have a number of things coming together to bring you to this state. However, it isn't a unique state and others have resolved it in various ways. 

I suspect that your advisor is a bit inexperienced at this and is genuinely unable to give you the guidance you need. That isn't uncommon. Some doctoral students in math come up with their own problems and some advisors provide problems to students. I don't know which is more common, actually. I was once refused by a potential advisor who told me he didn't think he had the experience to guide me properly. But he got me connected to a (scary scary) senior professor and it worked out fine. That professor was full of problems he was more than happy to share. 

Switching sub-fields isn't that uncommon either. Many students come to doctoral studies relatively "unformed", even with a master's degree behind them. But, working in a field that you like is a big help. For me it was an issue of insight. I had deep insight into classical real analysis and some aspects of topology. But actual insight into algebra was always hard for me. In analysis I knew what I could expect to be true before starting a study. I never had that sense in algebra. 

No, you aren't a failure. Whether you stay or go, do it for a reason related to what you really want to do. 

You may find a new situation to be similar or not, but you have some control over that. A more experienced advisor in a field you love, could be explored before you make any decisions. You can search for an alternative without making a prior commitment to actually change.