The problem is, UITableViewController's view property is the same thing as the tableView property.  I had the same problem, wanting to put some fixed content above the table.  I didn't want to change the base class, as it provides lots of great functionality I didn't want to lose or disrupt.
The fix is actually easy.  The trick is to create custom set and get for self.tableView property.  Then, in loadView, you replace the view with a fresh UIView and add the tableView to it.  Then you're free to add subviews around the tableView.  Here's how it's done:
In header:
@interface CustomTableViewController : UITableViewController
{
    UITableView *tableView;
} 
In .m:
- (UITableView*)tableView
{
    return tableView;
}
- (void)setTableView:(UITableView *)newTableView
{
    if ( newTableView != tableView )
    {
        [tableView release];
        tableView = [newTableView retain];
    }        
}
- (void)loadView {
    [super loadView];
    //save current tableview, then replace view with a regular uiview
    self.tableView = (UITableView*)self.view;
    UIView *replacementView = [[UIView alloc] initWithFrame:self.tableView.frame];
    self.view = replacementView;
    [replacementView release];
    [self.view addSubview:self.tableView];    
    //code below adds some custom stuff above the table
    UIView *customHeader = [[UIView alloc] initWithFrame:CGRectMake(0, 0, self.view.frame.size.width, 20)];
    customHeader.backgroundColor = [UIColor redColor];
    [self.view addSubview:customHeader];
    [customHeader release];
    self.tableView.frame = CGRectMake(0, customHeader.frame.size.height, self.view.frame.size.width, self.view.frame.size.height - customHeader.frame.size.height);
}
Enjoy!