How hard is it to solve for $P$ in $A = PBP^{-1}$?
Graph isomorphism has been well-studied.  A short summary: the graph isomorphism problem is not known to be in P (there are no known polynomial-time algorithms), but it is not believed to be NP-complete.  There are heuristic algorithms for  graph isomorphism that work extremely well on most instances that arise in practice.  Read the Wikipedia page on graph isomorphism for more.

As for your particular proposed approach: the Wikipedia page you linked to already explains why that method does not work in general.  That method only works if there are no repeated eigenvalues in the matrix corresponding to the adjacency graph.  Therefore, it will fail for graphs where there are repeated eigenvalues.  Such graphs cannot be ignored.  Consequently, that method may work for some graphs but it will fail (or work poorly) for other graphs, so it is not a general solution.

Graph isomorphism is not a good candidate for a basis for a cryptographic system, for two reasons.  First, existing heuristic algorithms are very good at solving the problem in practice, and it's not clear how to generate hard instances of graph isomorphism.  Second, and more seriously, to be useful for cryptography, we need to not only have a hard problem; we need to have a "hidden trapdoor" that the creator of the public key can embed, which makes the problem easy for the creator, but which is hard for anyone else to detect.  No one  knows how to embed such a "hidden trapdoor" into the graph isomorphism problem.