You can do it like this :

- Override the core K2 item form layout by copying the file 'components/com_k2/views/item/tmpl/form.php' to 'templates/YOURJOOMLATEMPLATE/html/com_k2/item/form.php'
- Edit this new file and add this js code to it (in 2.4.1, i've added this in line 208, just before the end of the K2 js part) :

window.addEvent('domready',function () {
$$('#catid option').each(function(item, index){
if (item.getProperty('disabled'))
item.remove();
});
});

I've just tested on a local website with Joomla! 1.5.20, K2 v2.4.1 and mootools 1.1/1.2

Done: 

I have edited ..\media\k2\assets\js\k2.js at the line 239 from 
$K2('#catid option[disabled]').css('color', '#808080'); 
to 
$K2('#catid option[disabled]').css('font-size', '0px');

window.addEvent('domready',function () {
                                $$('#catid option').each(function(item, index){
                                        if (item.getProperty('disabled'))
                                        item.remove();
                                });
                        });

$K2('#catid').change(function(){
                                if($K2(this).find('option:selected').attr('disabled')){
                                        alert(K2Language[4]);
                                        $K2(this).val('0');
                                        return;
                                }