Finally found the answer. Listed here for anyone searching...
The Theme needs to be turned off. To work with all versions of Windows here is the code:
void UpdateBackground(HWND hWndToolbar) {
HMODULE hTheme;
hTheme = LoadLibrary("UXTheme.DLL");
if (hTheme) {
void(WINAPI *SetWindowTheme)(HWND,void *,void *);
(FARPROC) SetWindowTheme = GetProcAddress(hTheme,"SetWindowTheme");
if (SetWindowTheme) SetWindowTheme(hWndToolbar,L"",L"");
FreeLibrary(hTheme);
}
SetClassLong(hWndToolbar, GCL_HBRBACKGROUND, (LPARAM) CreateSolidBrush(RGB(0,0,0xFF)));
}