Is the image that you are setting as your featured image in the post the size of the header image that is required for the theme that is listed at appearance > header? It needs to be the exact size (width). If the image is smaller, it will not be used as a featured header image.
From: http://wpbtips.wordpress.com/2010/08/23/featured-images/
Adventure Journal, Chateau, Coraline, Ocean Mist, Pilcrow, Twenty Ten, Vostok
Replaces regular header image when viewing single post or static page. For dimensions see my post Header images (cropped if larger, no show if smaller).