Make sure you put the logo on both the slide master and the title master. If
you don't have a title master, go to View|Master and then to Insert|New
Title Master.
The title master is what is applied to your slides that use the title slide
layout. The slide master is applied to slides that use any of the other
layouts (title + text, title + content + text, etc.).
Also check the slides using Format|Background and make sure you haven't
selected "omit graphics from master."