It looks like this falls into the "complicated but plausible, and being investigated" category - this is from a recent overview paper, "Pulsar timing and its applications", RN Manchester, 2017. Journal of Physics; arXiv.
Another interesting application of precision pulsar timing is to navigation of spacecraft that are distant from the Earth, even outside the solar system. [...] Analysis of a realistic simulation has shown that position location with an accuracy of better than 20 km is possible using observations of just four MSPs. Autonomous operation of the system is possible, but accuracy is improved with updates of the pulsar parameters from Earth-based observations. It is interesting to note that in 2016 the Chinese launched a satellite, XPNAV, dedicated to exploring X-ray pulsar navigation, and that NASA's recently launched NICER mission on the International Space Station has a project (SEXTANT) devoted to this topic as well.
There is a writeup of the 2018 NICER/SEXTANT project here; in the first run, they took 78 measurements of four pulsars over one day, and were able to find a location accurate to within ten miles, which is pretty good going. I haven't found an update on XPNAV.
However, there are definitely logistical questions. NICER is described as "about the size of a washing machine" (photo), and per the CRS-11 manifest it massed about 370kg. I don't know what its power requirements are, but I'm guessing they're not small - easy for the ISS, challenging for a smaller probe.
Granted you could probably strip it down quite a bit if you were just using it for navigation, rather than navigation being tacked on to scientific observing, but it feels like there is still a long way to go before you could bolt one of these onto something like Cassini or New Horizons.