Seu .profile será lido quando você efetua login não quando você inicia um novo shell. Isso inclui quando você faz o login em um gerenciador de exibição gráfico, o qual eu suponho que você esteja fazendo ("toda vez que eu ligo o terminal"). Se você estiver em uma interface gráfica, faça o logout completo dele e volte para obter um novo ambiente.
EDIT: Para referência futura, recomendo colocar coisas assim em um arquivo .bashrc em vez de .profile . O .bashrc é lido toda vez que um shell é iniciado. Esta página explica bem a diferença em mais detalhes.