When I start a bash terminal, my .profile is not being executed. I do not have a ~/.bash_profile or a ~/.bash_login, so .profile is supposed to run, right? What else could be wrong?
It's not a login shell.
If a shell is a login shell, it will look for .bash_profile if it exists, then .profile. Other shells look for .bashrc
So, you can put the things you want in every shell instance in .bashrc, and possibly have a reference that sources .bashrc in .profile.
end of .profile:
If you're using a graphical desktop, .profile should be sourced by your desktop manager. Lightdm does source .profile now, at least on Ubuntu. See: https://bugs.launchpad.net/ubuntu/+source/lightdm/+bug/794315
With kdm, and Kubuntu-12.04, the file /etc/kde4/kdm/Xsession gets sourced, which does the .profile including. Kubuntu-12.10 will probably use lightdm. Ubuntu 12.04 uses lightdm so that /usr/sbin/lightdm-session sources .profile.
I think the way to go is to (1) set/export environment settings in ~/.profile and (2) have .profile sourced by .bash_profile:
(and not have .bashrc sourced by either .profile or .bash_profile).