Check box stays in the unchecked state.

Just a guess (I don't know your application)... but is there another layer going on there?  I'm currently working with an application where, once I click on a control, there's another layer of objects that "takes over". We ran into a problem where clicking on a control appeared to "enable" the control on screen... but when we tried sending keystrokes to that control, we got errors indicating that we were unable to do so because the control was disabled. What we needed to do was click on the FIRST control to enable another control that is handling the actual UI actions.  

This is just a wild guess, mind you... but worth investigating.

Other things you can try is calling "ClickChecked" (which I think is an action for most check box controls).  You can also see if there is a "checked" property that you can just try setting to "true".  Not exactly simulating user actions and it carries it's own problems in that this might not fire certain events and such. But it's worth trying it to see if TestComplete can actually set the checkbox to the proper value.