Boas.
Obrigado pelas respostas, mas de facto eu não estava a fazer bem as coisas, eu não tinha posto a velocidade de relógio fora do atmega (com cristal fora do atmega), ou seja estava a utilizar o relógio interno do atmega e as velocidades de comunicação série não funcionam acima dos 9600.
Entretanto este projecto teve que parar um pouco (é que trabalho numa empresa de desenvolvimento de hardware e software) e também havia o problema (tal como dizem) de não ter o bootloader arduino gravado no atmega, e já agora posso gravar o bootloader arduino com o avrisp-u? Onde encontrar esse bootloader?
Ainda assim já encomendei um arduino duemilnove a nível pessoal que deve chegar para a semana

Muito e muito obrigado pessoal.