As a physiatrist doing a pain fellowship, i have to say it is not tricky to get in. I had 7 offers for joining fellowships, 5 from top anesthesia and 2 from top rehab based. Each have pro and cons, so I picked what was the best fit for me.
Rehabilitation med folks have a better understanding of neuroanatomy, musculoskeletal examination, EMG and overall diagnostic skills. Anesthesia grads on the otherhand have better technical skills of needle manipulation and medication knowledge. Somewhere in the middle of the fellowship, the anesthesia fellows learn all about the MSK skiils and Rehab folks learn the technical aspect.
Conclusion: do the residency you think fits your personality and interest. fellowship is something you will have no problem with if you are good in what you do.
good luck