To add new user to the web is very common process but fails most time. See http://sharepointsearch.com/cs/blogs/sharepointblogs/archive/2007/12/20/using-spweb-ensureuser-loginname-to-add-a-new-spuser-to-a-web.aspx for more details.
The way to solve this problem is to user SPWeb.EnsureUser(loginName).The description in the SDK for EnsureUser is:
“Checks whether the specified login name belongs to a valid user of the Web site, and if the login name does not already exist, adds it to the Web site.” Which happens to be exactly what we want!
Now we can finish our code:

   SPUser newUser = newWeb.EnsureUser(@"domain\username");
   newWeb.AllowUnsafeUpdates = true;

   // Create the new roleassignment that we want to add to the collection of roleassignments of the new web
   SPRoleAssignment roleAssignment = new SPRoleAssignment(newUser);
   SPRoleDefinitionBindingCollection roleDefBindings = roleAssignment.RoleDefinitionBindings;
   // Add the binding to the correct roledefinition to the roleassignment
   // This can also be Contribute for contributor rights.
   // Keep in mind that in sites in other languages this needs to be translated
   newWeb.AllowUnsafeUpdates = false;