You could use an external RC combination to remove the de-bounce before it gets to the interrupt pin.
What does the rest of your code look like? I ask because if it were me I'd use the millis() function to produce some code that operated every milli second and use a simple statemachine to handle the reading and de-bouncing of the switch.
Regards,
Mike