Well it turns out the answer is in later in the video I linked to! The solution is to change the server location settings. Right-click Tomcat server in the Eclipse server list, and click Open. Change server location to "User tomcat installation" and then it works.
subject: 404 error with Tomcat immediately after installation (not working out-of-box)