Sorry for the late response, Brandon.
I was talking about the normal Search functionality. I was talking about the textbox on the Users Admin page. The box will filter on username and email. I had to extend it to also filter on some fields of the user profile.
It was purely a lack of time that made me do this but I went ahead and edited the users module to get the job done. :(
I will revisit and roll out those changes later. I suspect I'll have to write a custom module to do what I need.