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
If all you're using it for is aliases, I woud recommend you name the file ~/.bash_aliases:
if [ -f ~/.bash_aliases ]; then
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.