The steps reported above are correct but a bit more information was needed, because it can be misleading. For reference, my phone is the Droid X variant of Android.
Go to: Settings > Accounts
Within this screen you should be able to identify your YouTube account. Mine was
<username>@youtube.com.
Long Press on the account you wish to remove.
A pop-up appears with only one option, "Open Account"
Click on "Open Account" (this is likely where many people get confused; "I don't want to open the account, I just want to delete it!" Trust me, this is where you need to go)
The next screen that appears now shows a "Remove Account" button at the bottom. Click "Remove Account" and acknowledge the "are you sure" pop-up.
Account has now been removed and will not automatically appear next time you access the app.
