We present accurate ab initio and quantum scattering calculations on a prototypical hybrid ion-atom system Yb\(^+\)-Rb, recently suggested as a promising candidate for the experimental study of open quantum systems, quantum information processing, and quantum simulation. We identify the second-oder spin-orbit (SO) interaction as the dominant source of hyperfine relaxation and decoherence in cold Yb\(^+\)-Rb collisions. Our results are in good agreement with recent experimental observations [L. Ratschbacher et al., Phys. Rev. Lett. 110, 160402 (2013)] of hyperfine relaxation rates of trapped Yb\(^+\) immersed in an ultracold Rb gas. The calculated rates are 4 times smaller than predicted by the Langevin capture theory and display a weak \(T^{-0.3}\) temperature dependence, indicating significant deviations from statistical behavior. Our analysis underscores the deleterious nature of the SO interaction and implies that light ion-atom combinations such as Yb\(^+\)-Li should be used to minimize hyperfine relaxation and decoherence of trapped ions in ultracold atomic gases.