Maybe you have mode promotion turned on?
If yes: Try turning it off and see what happens!
Although I don't know much about OS3.9 (still very satisfied with 3.1 :-)), maybe there's some argument you could pass to SetPatch in case it tries to do some FBlit-like hack (IE use the CPU instead of the blitter, store Images in fast-ram etc.)
Also check that you have the newest picture datatypes installed!
