It could very well be that your new external is not selected as the target disk.
1. Start System Preferences
2. Select your Time Machine Preferences
3. Select a new target for your Backups (your external)
4. Begin backing up
5. Label that external hard disk as your backup disk and treat it as if it were a collection of very important documents (since that's what it is)