You're told to set your path in your
~/.bash_profile, but Gnome doesn't source this when you bring up a terminal (nor has it already been sourced in Gnome's startup). What to do?
Simple: Gnome's startup does run through /bin/sh, which sources
~/.profile. Any changes you make in there will take effect when you next log in.