If you really are using a UIToolbar (note the lower-case "b") and not a UINavigationBar, there is a very easy way to change the buttons and have the transition automatically fade without dropping to Core Animation.
If you're using Interface Builder, you'll need a reference to the toolbar in your code. Create an IBOutlet property and link the toolbar to it in IB:
@property (nonatomic, retain) IBOutlet UIToolbar *toolBar;
This will allow you to reference the UIToolBar as self.toolBar. Then, create your new buttons and add them to an NSArray and pass this to the -[UIToolbar setItems:animated:] method as follows:
UIBarButtonItem *newItem = [[[UIBarButtonItem alloc]
initWithBarButtonSystemItem:UIBarButtonSystemItemDone
target:self
action:@selector(handleTap:)] autorelease];
NSArray *newButtons = [NSArray arrayWithObjects:newItem, nil];
[self.toolBar setItems:newButtons animated:YES];