あなたの問題は Python とは関係がないようですが、分解しようとしている文字 (u'\u0153' - 'œ') は構成自体ではありません。
コードが「ç」や「ã」などの通常の複合文字を含む文字列で機能することを確認します。
>>> a1 = a
>>> a = u"maçã"
>>> for norm in ('NFC', 'NFKC', 'NFD','NFKD'):
... b = unicodedata.normalize(norm, a)
... print b, len(b)
...
maçã 4
maçã 4
maçã 6
maçã 6
そして、両方の文字 (あなたの文字と c + cedila) の Unicode 参照を確認すると、後者には前者にはない「分解」仕様があることがわかります。
http://www.fileformat.info/info/unicode/char/153/index.htm
http://www.fileformat.info/info/unicode/char/00e7/index.htm
「œ」は正式には「oe」と同等ではないようです-(少なくともこのユニコード部分を定義した人々にとっては)-したがって、これを含むテキストを正規化する方法は、文字を手動で置き換えることですunicode.replace を使用したシーケンス - ハッキーに聞こえるかもしれません。