I'm a little confused by your saying "I ran the xs portion first" as to whether the problem is with Class::Date or with your module. First you should just test whether Class::Date works. E.g.:

  export PERL5LIB=$HOME/lib/whatever
  perl -MClass::Date -le 'print 1'
[download]

If that doesn't work, you should tell us more about exactly how you built it, what OS and version of Perl you're on, etc.