sounds like the threads in the holes may just be a little boogered up, or just full of crap that needs cleaned out--take one of the bolts and carefully cut 2 or 3 "flutes" in it (ie, make it into a tap/thread chaser, using a hacksaw or small cut off saw) and then turn it in and out of the hole, while keeping your mind out of the gutter--obviously don't crank on it too hard so that u don't snap off the bolt (or worse, crack the block there...), and if this works, don't take it in too deep
don't know if that is the problem, but sounds like a place to start since u said the bolts will start in the holes