logged in as a user and getting the following error when trying to create a record: "There is no valid license for the current user." Any ideas why this is happening?

First thing I'd do is create a user saved search for users with login access = true, inactive = false. Compare the number of results to the number of licenses in Setup > Company > View Billing Info. The system should stop you creating more users than licenses, but I've seen active users go beyond licensing limits on the odd occasion.