The file .bash_profile is probably not being read by your shell on launch. Many distros have something like this in their default .bashrc:
if [ -f ~/.bash_profile ]; then
. ~/.bash_profile
fi
If all you're using it for is aliases, I woud recommend you name the file ~/.bash_aliases:
if [ -f ~/.bash_aliases ]; then
. ~/.bash_aliases
fi
All it does it checks if the file exists, and if so, executed the commands in it. In your case, the alias commands.
Pop that in your .bashrc and your problems should be solved.
EDIT: Actually it's a little more complicated than that. My solution will work, but this is worth reading .bash_profile vs .bashrc
P.S. A reboot rarely is necessary to fix a problem on a *nix system. A logout and login at most.