Eu vejo que você descobriu uma solução alternativa, mas algo que pode ser um pouco melhor e mais elegante para você, seria abrir /home/server/Desktop/minecraft/craftbukkit.sh
em um editor de texto e adicionar:
# before anything is done, probably top of the script (but under the #!/bin/sh)
PWD=$(pwd) # save the previous location
cd /home/server/Desktop/minecraft
...
...
...
...
# after everything is done, probably near bottom of the script
cd $PWD # restore the previous location
Se o diretório atual for o problema (como você sugeriu na sua solução), isso deve permitir que você inicie o script de qualquer lugar e ele funcionará bem.