<p>I am writing a Java utility that helps me to generate loads of data for performance testing. It would be <em>really</em> cool to be able to specify a regex for Strings so that my generator spits out things that match this.</p>
<p>Is something out there already baked that I can use to do this?  Or is there a library that gets me most of the way there?</p>

You'll have to write your own parser, like the author of String::Random (Perl) did. In fact, he doesn't use regexes anywhere in that module, it's just what perl-coders are used to.
On the other hand, maybe you can have a look at
the source
, to get some pointers.
EDIT: Damn, blair beat me to the punch by 15 seconds.