The cross-browser solution that worked for me was to include an empty label (with class "checkbox_label") after the checkbox input and then style IT rather than the checkbox.
input[type=checkbox] + label:after
{
content: url(images/unchecked_after.gif);
position:relative;
left:0px;
top:1px;
z-index:100;
}
input[type=checkbox]:checked + label:after
{
content:"";
}
.checkbox_label
{
height:0px;
width:0px;
display:inline-block;
float:left;
position:relative;
left:20px;
z-index:100;
}