Yes, basically we build with nocheck, and we run all the tests separately on the installed packages (not as a part of the build process itself). You can see the logs here: http://buildbot.askmonty.org/buildbot/builders/kvm-deb-wheezy-amd64/builds/3175 .
It makes us miss some problems which affect running tests on an out-of-source build.
The debian expert, otto, builds in a more traditional fashion and reports problems to us (and solves many of them himself). You can seek his advice here or on #maria channel. MDEV-5591 was not fixed in 5.5 because it was agreed that we should incorporate Otto's changes instead.
The problem you encountered is MDEV-7359, it will be fixed in the next release. As a workaround, Otto removed the new block which looks for the replace utility, you can try the same (apparently it was introduced in MySQL 5.5 to solve a problem on Windows, merged into MariaDB 5.5, but didn't get along with MariaDB's variation of MTR).
Thanks. I actually handle the problem the way I've described (the latest one by changing "$basedir/extra/replace" to "$basedir/builddir/extra/replace" in mysql-test/mysql-test-run.pl line 2497). I just thought some feedback might come in handy for you to make MariaDB even better and be able to build Debian packages with tests (which is the default) out of the box 
Our build process uses debian/autobake-deb.sh which is, in fact, a documented recommended way to build deb packages https://mariadb.com/kb/en/mariadb/documentation/getting-started/compiling-mariadb-from-source/building-mariadb-on-ubuntu/ (the page is for Ubuntu, but still).
While I agree that running the build with tests is technically a right thing to do, it would add even more burden on our already overloaded build system. We run tests on packages installed more or less the way a user would install them, and from an average user perspective it seems more important than running them upon a build. So, we would have to add build-time tests to post-installation tests, thus duplicating them. That's something we might not be able to afford.
That said, we should definitely have at least one builder which would run tests on an out-of-source builds. Or rather two builders, Linux and Windows.
The workaround with adding builddir can of course be only applied locally, it's not a generic solution.
Don't worry, I can report you should any new problems with tests on Wheezy arise (there are already two) I need some customisations to the package so I build every new release myself. Running tests in such case is indeed desirable.
Closing as a duplicate of MDEV-7359