It is possible for the Terminal.app to start a specific shell for new windows instead of your login shell. Open the Terminal.app preferences panel.
On the General tab, there is an option called "Shells open with:". Normally "Default login shell" is selected, but it's possible to specify a different command.
If you have ever clicked on "Command (complete path)", the default path is "/bin/bash" which would give you the behavior you are experiencing. If this is the case, just reselect "Default login shell"
Additionally, another way to confirm that you have actually changed the shell on your user account is to run
chfn... all the same program) from your regular account without sudo, and without any command-line arguments. It will prompt for your password, then open an editor window to allow you to edit several attributes of your Unix user account at once. One of the lines of the file you are editing will list your shell. Mine says:
... meaning I have not changed my default shell. If yours still says that, you can edit that line to say
Shell: /usr/local/bin/bash and it will make the update.