We often see people on here chasing alternative theories, after a bit of work has resulted in changes. Every time, it is important first to verify the recent work done, as that is the only change. Whilst there is the possibility that other faults could occur when another change has happened, this is rare, unless damage has been caused, or other stuff has been disturbed.
For me, I'd want the physical timing checked properly, with the correct tools, before chasing down blind alleys. As the car ran fine before the cambelt change, the garage must sort this problem free. If they're not willing to do so, take the car away, seek other professional advice, and report the matter to Trading Standards, and be prepared to claim all the initial money back. As soon as they considered that the original state was 2 teeth out, they should have stopped, and made sure they were doing it right.
The ECU starts with its base setting, but 'learns' as it goes, to adjust timing and fuelling to accomodate wear, and driving style. This forum has exprienced this engine running one or two teeth out before, and seemign fine. It is possible that the ECU is learning its new state, and regaining some of the lost performance. Whilst it might seem much better, coming from a state of poor performance, any increase is felt.