if its a les paul style guitar the bridge might have lowereed a bit whilst u where changing the strings. normaly when u increase the tension of the strings the action (distance between te strings and fretboard) increases. so it seems od to me that in your case it has not.
there are two ways to fix the problem alter how the bridge is set up or alter the truss rod. the later i suggest you have a tech do because if u do it wrong u could really screw up ur guitar. if u do do it do it very slowly because if it is done too fast the neck can be damadged.
hope this helps