Terminal won't choose new window settings at startup
It sounds like Lion's resume feature is confusing the cause-effect relationship between settings and application behavior. 

The "On Startup, open" should work, assuming that you had no windows open when you closed Terminal.app.  Lion's resume feature is enabled for Terminal.app by default, so quitting the application before closing any windows will yield the same windows the Terminal is re-launched. 

The simplest fix is this:


Make sure you've closed all Terminal windows.  
Restart Terminal.app.  


In the normal course of events, the resulting window should have the "On Start, open..." settings. If the steps above do not fix the issue, then I recommend deleting your Terminal preferences with a backup so that you can revert if needed. 



Disable Resume for Terminal.app

You can also just disable resume for Terminal.app. Run the following command and re-launch Terminal.app twice:

defaults write com.apple.Terminal NSQuitAlwaysKeepsWindows -bool false