Não posso lhe dar o passo a passo (solicitação de recurso #34354 ajudaria, exceto que provavelmente não seria portado para o MySQL 5.0), mas o tempo extra é devido ao fato de que um ALTER ... CHANGE pode alterar o tipo da coluna (e os atributos da coluna, se houver), o que exige a conversão dos valores armazenados na coluna e outras verificações. O MySQL 5.0 não inclui otimizações para quando o novo tipo e atributos são iguais aos antigos. Da documentação para ALTER no MySQL 5.0:

Em 5.1, ALTER tem algumas otimizações adicionais: