When multiple content types are used, Document Templates are managed one per content type.  The following steps walk through uploading a new document template for a content type and assigning it to a document library.

1. Go to Site Actions à Site Settings à Modify All Site Settings.
2. Click on Site Content Types under Galleries.
3. Click on the Content Type that is to be changed.
4. Click on Advanced Settings under Settings.
5. Choose to upload a new document template and browse out and select the file.  Click Ok to save changes.
   
6. If the content type has not been added to the document library, browse to the Document Library where the Content Type will be used and go to the settings of the library.
   
7. Select to Add from existing site content types under Content Types.
   
8. Add the content type and click Ok.
   
9. Browse back to the document library.  The new document template associated with the added content type now appears under the New Button.