Found user with uid of 0 (zero) in users table... huh? Is it normal to have a user with uid of 0 in users table?
It is normal, as Drupal creates that entry when it is installed, for the anonymous user.  That is done from user_install() (Drupal 7), or system_install(), which contain the following code.

  // Drupal 7.
  // Insert a row for the anonymous user.
  db_insert('users')
    -&gt;fields(array(
    'uid' =&gt; 0, 
    'name' =&gt; '', 
    'mail' =&gt; '',
  ))
    -&gt;execute();




  // Drupal 6.
  // Inserting uid 0 here confuses MySQL -- the next user might be created as
  // uid 2 which is not what we want. So we insert the first user here, the
  // anonymous user. uid is 1 here for now, but very soon it will be changed
  // to 0.
  db_query("INSERT INTO {users} (name, mail) VALUES('%s', '%s')", '', '');
  // …
  // This sets the above two users uid 0 (anonymous). We avoid an explicit 0
  // otherwise MySQL might insert the next auto_increment value.
  db_query("UPDATE {users} SET uid = uid - uid WHERE name = '%s'", '');  


That entry is normally used when joining the data contained in the "node" table with the data contained in the "users" table.

Not having that entry would cause Drupal not to work correctly in some circumstances.

If you need to restore the anonymous user data in the database, I would execute code similar to the one executed from Drupal. In particular, for Drupal 6, I would execute the following code.


If the data for the anonymous users already exists in the database, but the user ID is not 0:

db_query("UPDATE {users} SET uid = uid - uid WHERE name = '%s'", '');

If the data for the anonymous user don't exist, even with the wrong user ID:

db_query("INSERT INTO {users} (name, mail) VALUES('%s', '%s')", '', '');
db_query("UPDATE {users} SET uid = uid - uid WHERE name = '%s'", '');



If you want to automatically restore the anonymous user data, you could implement hook_cron() in a custom module, and execute code similar to the following one. (The code is for Drupal 6.)

function mymodule_cron() {
  $uid = db_result(db_query("SELECT uid FROM {users} WHERE name = '%s'", ''));

  if ($uid === FALSE) {
    // The data has not been found in the database; re-create the row.
    db_query("INSERT INTO {users} (name, mail) VALUES('%s', '%s')", '', '');
  }

  db_query("UPDATE {users} SET uid = uid - uid WHERE name = '%s'", '');
}


If you give to the module a lower weight, its implementation of hook_cron() will be executed before the other implementations, and this would avoid they will fail because the missing row in the database.