How to unit test my models now that I am using Core Data?

You need to build a Core Data stack, either within each method or in -setUp and then tear it down. Using an NSInMemoryPersistentStore will keep things fast and in-memory for your unit tests. Add a @property (nonatomic,retain) NSManagedObjectContext *moc to your TestCase subclass. Then:

- (void)setUp {
  NSManagedObjectModel *mom = [NSManagedObjectModel mergedModelFromBundles:[NSArray arrayWithObject:bundleContainingXCDataModel]];
  NSPersistentStoreCoordinator *psc = [[NSPersistentStoreCoordinator alloc] initWithManagedObjectModel:mom];
  STAssertTrue([psc addPersistentStoreWithType:NSInMemoryStoreType configuration:nil URL:nil options:nil error:NULL] ? YES : NO, @"Should be able to add in-memory store");    
  self.moc = [[NSManagedObjectContext alloc] init];
  self.moc.persistentStoreCoordinator = psc;

  [mom release];
  [psc release];

}

- (void)tearDown {
  self.moc = nil;
}

Your test method then looks like:

- (void)test_full_name_returns_correct_string {
    Patient *patient = [NSEntityDescription insertNewObjectForEntityForName:@"Person" inManagedObjectContext:self.moc];

    patient.firstName = @"charlie";
    patient.lastName = @"chaplin";
    STAssertTrue([[patient fullName] isEqualToString:@"charlie chaplin"], @"should have matched full name");
}

assuming your entity is named Person. There was a memory leak in your version of the method, by the way; patient should be -release‘d in the non-Core Data version (insertNewObjectForEntityForName:managedObjectContext: returns an autoreleased instance).