Tambien tuve ese problema, lo que ise fue crear un DockPanel, y dentro de este tengo un TextBlock y un Image.
Asi que es el TextBlock va el texto y en la Image ira la imagen, despues los agrego al DockPanel.
Una vez esto, agrego el DockPanel al Header del TreViewItem y listo.
Ahi te va el codigo.
Código C#:
Ver originalDockPanel dockPanel1 = new DockPanel();
TextBlock textBlock1 = new TextBlock();
Image img = new Image();
string imgTree = "pack://application:,,,/MAES.UI.WPF;component/MyResources/ImagesTree/folder.bmp";//ruta de la Imagen
img.Source = new BitmapImage(new Uri(imgTree));
textBlock1.Text = header.ToString();
dockPanel1.Children.Add(img);
dockPanel1.Children.Add(textBlock1);
TreeViewItem tv= new TreeViewItem() { Header = dockPanel1 };