Use set_levels:

In [22]:
df.columns.set_levels(['b1','c1','f1'],level=1,inplace=True)
df

Out[22]:
     a         d
    b1   c1   f1
0    1    2    3
1   10   20   30
2  100  200  300

rename sets the name for the index, it doesn't rename the column names:

In [26]:
df.columns = df.columns.rename("b1", level=1)
df

Out[26]:
      a         d
b1    b    c    f
0     1    2    3
1    10   20   30
2   100  200  300

This is why you get the error

You could try:

df.columns = pd.MultiIndex.from_tuples(df.rename(columns = nested_columns).columns)
df 

Output:

  One     Two    
    a   c   b   d
0  27  67  35  36
1  80  42  93  20
2  64   9  18  83
3  85  69  60  84

Since pandas 0.21.0 the code should be like this

def rename_unnamed(df):
    """Rename unamed columns name for Pandas DataFrame

    See https://stackoverflow.com/questions/41221079/rename-multiindex-columns-in-pandas

    Parameters
    ----------
    df : pd.DataFrame object
        Input dataframe

    Returns
    -------
    pd.DataFrame
        Output dataframe

    """
    for i, columns in enumerate(df.columns.levels):
        columns_new = columns.tolist()
        for j, row in enumerate(columns_new):
            if "Unnamed: " in row:
                columns_new[j] = ""
        if pd.__version__ < "0.21.0":  # https://stackoverflow.com/a/48186976/716469
            df.columns.set_levels(columns_new, level=i, inplace=True)
        else:
            df = df.rename(columns=dict(zip(columns.tolist(), columns_new)),
                           level=i)
    return df

That is indeed something missing in rename (ideally it should let you specify the level).
Another way is by setting the levels of the columns index, but then you need to know all values for that level:

In [41]: df.columns.levels[0]
Out[41]: Index([u'1', u'2'], dtype='object')

In [43]: df.columns = df.columns.set_levels(['one', 'two'], level=0)

In [44]: df
Out[44]:
        one                 two
          A         B         A         B
0  0.899686  0.466577  0.867268  0.064329
1  0.162480  0.455039  0.736870  0.759595
2  0.620960  0.922119  0.060141  0.669997
3  0.871107  0.043799  0.080080  0.577421

In [45]: df.columns.levels[0]
Out[45]: Index([u'one', u'two'], dtype='object')