Personally, I love Test::Deep, and I use it quite often internally for testing. However, I might be wary of including into a public module since Test::Deep itself has many dependecies:

Test::More => '0',
Test::Tester => '0.04',
Test::NoWarnings => '0.02',
Scalar::Util => '1.09',
List::Util => '1.09',
[download]

(which themselves may have more dependencies too, its been a while since I installed Test::Deep, so I dont recall).

However, I do make heavy use of Test::Exception in a lot of the test suites of my modules on CPAN, and I do require it in the Makefile.PL. I will usually comment in the README file that it is for the test suite only, so the user could choose to ignore it I suppose. Of course, that too does have its dependencies:

Test::Builder => 0.13,
Test::Builder::Tester => 0.08,
Test::More => 0.44,
Sub::Uplevel => 0.06,
[download]

I think what you need to ask yourself is, how important are the Test::Deep tests to the overall functionality of your module? Do they test critical parts, or edge cases? Can you write equivalent Test::More tests without too much trouble? Your example code looks like is_deeply might be able to handle it, are you actual tests any more complex?

My personaly opinion is that you should include it. Having to download and install dependencies, if you are using CPAN is pretty trivial (if you configure it as such). Anyone who really complains about having to wait that extra few seconds is likely someone who wont run make test in the first place.