From what you posted I would agree with Milan and suspect the new cat too. If you can post the 4 gas readings and Lambda at high idle as well as comfirm the O2 sensor switching properly (range as well as frequency) that could help.
Dont be put off by the spontaneous outbreak of theory discussion