Can you post a code sample of the situation in which you're getting this message?

Are you referring to creating a User in Test Code, or just for "general" testing (i.e. actually creating a new User record)?

Here is some code for creating a User at a specified Profile in Test Code:

// Some of the fields necessary to create a User account
// should be populated based on whichever User is running tests.    
private User DummyUser {
	get {
		if (DummyUser==null) {
			DummyUser = [select id, TimeZoneSidKey, LocaleSidKey, 
				EmailEncodingKey, ProfileId, LanguageLocaleKey
				from User limit 1];
		}
		return DummyUser ;
	} set ;
}

// Creates a Test User with a given Profile
private User createTestUser(String firstName,String lastName,String email,String userName,Id profileId) {
	return new User(
		FirstName = firstName,
		LastName = lastName,
		Email = email,
		Username = userName,
		ProfileId = profileId,
		Alias = lastName.substring(0,5),
		CommunityNickname = lastName.substring(0,5),
		TimeZoneSidKey=DummyUser.TimeZoneSidKey,
		LocaleSidKey=DummyUser.LocaleSidKey,
		EmailEncodingKey=DummyUser.EmailEncodingKey,
		LanguageLocaleKey=DummyUser.LanguageLocaleKey
	);
}

// Create a Test User with the Profile 
// of whoever is running the tests
private User createTestUser(String firstName, String lastName, String email, String userName) {
	return createTestUser(firstName,lastName,email,userName,DummyUser.ProfileId);
}

// For instance, if you want to create a user 
// with the Salesforce Platform License,
// you could grab the "Standard Platform User" Profile
//  and use this to create a test user
Profile platformUser = [select id from Profile where Name = 'Standard Platform User'];
User testUser = createTestUser('Joe','Smith','joe@acme.com','joe@acme.com',platformUser.Id);
insert testUser;

Also, if you're in test code and its telling you that you're out of licenses, increase the API version of your Apex class --- I believe some really old (i.e. Winter 10 or earlier) version of Salesforce wouldn't let you create new users in test code unless you had actual licenses for them. But this has long since been fixed.