I usually test my exceptions using Test::Exception, but I don't know if it plays well with the Error module.

It should behave perfectly. Error is just some syntactic sugar around Perl's normal exception handling system. The OP's test would become the IMHO much more readable:

use Test::More tests => 2;
use Test::Exception;

BEGIN { use_ok( 'MyModule' ) };

throws_ok { MyModule->foo( 'badparam'' ) } 'MyModule::Exception';
[download]