A curious error, this - any part of Moodle that searches the database of users (when adding staff to a course page, when showing a list of all users, when trying to add someone to your instant messaging Contact list) returns zero results. This means we can't add teachers to pages!
The accounts are there, though, and in fact listing all users (Administration -> Users -> Edit User Accounts) gives a 0 user count, but all the accounts are listed underneath it. You can use the A-Z firstname/surname shortcuts fine, and the lists they pull up are accurate, but the search function itself does not. i.e. clicking Firstname J and Surname S will return a list of users including John Smith, but a search for John Smith returns no results.
Presume this is a database connection error, though I've no idea how it happened!
We're on Moodle 1.5.2+ (on IIS 5.1) and upgrading to 1.6 very soon, this process may solve our problem but I'm fascinated to know how the hell it happened in the meantime!