Suponho que você esteja usando o InnoDB (você deveria de qualquer maneira ....)

Portanto, leia o capítulo a seguir do MySQL 2ed de alto desempenho, p.117:http://books.google.com.hk/books?id=BL0NNoFPuAQC&lpg=PA117&ots=COPMBsvA7V&dq=uuid%20innodb%20clustered% 20index%20high%20performance%20mysql&pg=PA117#v=onepage&q&f=false

Em geral, UUID é uma escolha ruim do ponto de vista de desempenho (devido ao índice clusterizado) e eles têm um benchmark para provar isso.