After some digging around in the core, specifically user.module, I found that when the user edit page is displayed, the system checks whether the user (the user who is seeing the edit page, not the user being edited) has permission to administer access control, and if so, grants them the ability to edit roles.
It turns out that in order to edit roles, the user must be given privileges to edit the access rights of all the roles, which is not really the same thing! In my opinion, there should be sufficient granularity between assigning roles to users and deciding what permissions those roles have. Perhaps this is something for a future Drupal release? It might even exist in Drupal 6 or Drupal 7, but not having played with them yet, I don't know.