The main theoretical problem with black holes is the information loss due to the no hair theorem. Look up "Black hole unitarity".
Another problem is that hawking radiation can send out anything, with no regard to the quantum numbers of what when in - so you put in a proton and return photons, which normally is impossible (conservation of the baryon/lepton/parity number).
No one really knows it that will really happen though, it's all theories and ideas.
But a black hole is not so much a prediction of relativity as it's the point where relativity fails. In that sense it was predicted by it, but relativity can not explain what happens in a black hole.