I was able to get this working simply doing this: (Since I'm only dealing with integers, going out of my way to bind the list of many possible status keys seemed to be overkill)
foreach($statuses AS $key => $status) {
$statuses[$key] = (int) $status;
}
$imploded = implode(",", $statuses);
$Criteria->condition = "statusId IN ($imploded)";
So I may go your route, but this is a 'Simple' way to do it.