How long have you been out of school? Where are you working now? If you do a residency, what do you plan to do when you finish? These are questions you should consider before you start lining up LORs. I agree with your coworker that if you don't plan to go into academia or move to a large city, a residency probably won't do your career much good. Also remember that if you do a residency, you will be job hunting again in a year, and that's extremely difficult in this economy. If you like the job you have, I would strongly suggest NOT doing a residency.
Now, supposing you decide to do a residency: It's not too late in the cycle to think about LORs. The deadline for the Match is usually early January and apps are usually due early-mid January, so you can probably wait till November to ask people for letters. I've seen a few apps from people who've been out of school for some time and they usually asked supervisors, coworkers who were big names in the field (e.g. officers in the ASHP state affiliate), or profs who they'd kept in touch with.
