Also what is the version of PHP that you are using?
I just found that if you are using PHP version less than 5.3 there was some problem. I just fixed it in and released v5.1 of the plugin.
Kindly try the latest version of the Bulk Delete plugin and let me know if you are still facing issue with this.