If "the document is locked from user editing" as you say, it's difficult to see how you're going to add a logo to it. That said, I believe what you're referring to as being "locked from user editing" is the template, rather than the document created from it; perhaps you could check that.

__________________
Cheers,
Paul Edstein
[Fmr MS MVP - Word]