以前、composerを入れるときに、こちらの記事を書いたのですが、自分が使っているVPSではこの方法で入りませんでした。
調べるとみるとPATHが /usr/local/bin ではなく /usr/bin でした。
なので composer.pharを /usr/bin/composer に置いたところ composer -v が正常に認識されました。
Linuxのパスですが、 echo $PATH で簡単にわかります。
また優先度などもありますので、パスが通っているはずなのに動きが違う・・・という方は下記リンクで調査しておきましょう。
参考リンク