So why the speed is different? Is it because of the faster clock speek on UNO?
Probably.
But I thought the example would have taken this into account when I change the board setting in the arduino menu.
It's not guaranteed. There's plenty of ways to code a sketch that make it depend on a particular clock speed (in fact getting timing
right is one of the most difficult parts of Arduino coding).
And why the flickering disappears on the Nano but not the UNO?
The clock/data signals to the TLCs will be running half as fast. Slow is more reliable for communication links.
I still say it's a decoupling problem. Where are you getting the 5V for the LEDs from? Try adding decoupling there.