I had similiar problems some time ago and I could only blast when I had been in the directory where blast was installed. Even though I set all shell variables correctly. If you do not solve this problem think about installing WU-blast instead of NCBI. It might also be faster.