I learned something about Objective-C trying to figure this one out.
Your basic problem is that the class of an object created by alloc'ing NSMutableAttributedString is not NSMutableAttributedString (always be wary of toll-free bridged classes). To get your code to work, try the following:
NSMutableAttributedString *realMutable = [[NSMutableAttributedString alloc] init];
id mutable = [OCMockObject niceMockForClass:[realMutable class]];
id string = [OCMockObject niceMockForClass:[NSAttributedString class]];
[[[mutable expect] andReturn:@"YO" ] initWithAttributedString:string];
NSLog(@"MOCK: %@", [mutable initWithAttributedString:string]);
[mutable verify];
// Outputs 'MOCK: YO' and passes