Check the following things:
1 - Make sure your IExceptionHandler class is prefixed by the attribute [ConfigurationElementType(typeof(CustomHandlerData))]
2 - Make sure your IException Handler class has not only a public constructor, but a public constructor that accepts a NameValueCollection argument. I.e.
public MyHandlerClass(NameValueCollection collection) {}
3 - Are you calling ExceptionPolicy.HandleException(exc, "YourExceptionPolicyName") ? If not, add that to where you catch exceptions globally, such as Global.asax's Application_Error in a web application.
4 - Check your web.config setup. The add node has a type="X, Y" property where X is the name of your class and Y is the assembly.
<exceptionHandling>
<exceptionPolicies>
<add name="My Exception Policy">
<exceptionTypes>
<add name="All Exceptions" type="System.Exception, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089"
postHandlingAction="None">
<exceptionHandlers>
<add type="CustomExceptionHandler, MyAssemblyThatContainsHandler, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null"
name="CustomExceptionHandler" />
</exceptionHandlers>
</add>
</exceptionTypes>
</add>
</exceptionPolicies>
</exceptionHandling>