For those that have been following this thread, I did finally find what the problem was. Unfortunately I don't have the time right now to figure out why it's a problem and therefore would not feel comfortable submitting a patch with an explanation.
The problem was with the following line in location.module: $result = pager_query(db_rewrite_sql($query), 10, 0, $count_query, db_rewrite_sql($query_args));
Specifically, it was the db_rewrite_sql method. Removing it results in the following line: $result = pager_query($query, 10, 0, $count_query, $query_args);
This works. I read through the api documentation for a bit at http://api.drupal.org/api/function/db_rewrite_sql/5 and believe it has something to do with "nid is rewritten if needed" since I was getting an "nid is ambiguous" error earlier. However since I can't be positive as to why that function was being used and whether it is indeed necessary in certain cases, I will refrain from submitting a patch.
I will review this more thoroughly when I have more time, but I wanted to thank all those that helped with the approach to take for debugging this. Not only did it help me in this case but I have a much better idea of what to do to debug module issues in the future.
Thanks everyone, .sander