My .net had been badly affected by Penguin and it's time to move on or sink I think.
Jez, I agree with phranque that the move from the brand.net to the brand.co.uk should be seen as a
"massive link disavowal". I believe that the move should work in the case of Penguin,
assuming that...
a) all your problems were link-related (with no spammy onsite techniques)...
b) there had been no additional promotion of brand.co.uk (ie, links built to it and redirected to the .net).
c) the new links you build are not artificial.
For reasons I'll mention in a moment, I don't think that Google would hold the previous association against you, but Google will be watching carefully how you build your new backlinks.
I'm assuming in this scenario that your old brand.net domain might become a placeholder, advising of the change, with a manual nofollow link taking traffic to the .co.uk. Any other kind of traffic redirection, even perhaps a meta refresh, I assume, might be seen as a "sneaky redirect".
Several questions I would start pondering, as you would in effect be starting over with zero inbound link juice....
Is your content now good enough to earn freely given editorial links? Do you have a customer base and customer loyalty? If so, then to that degree, the "brand" of brand.net has some aspects of a genuine brand. Can you make use of that? To do so might require creating some buzz online about the brand name change, perhaps to build new inbounds, get people talking about your new site. Your .net placeholder should be a really good page advising of the change.
Does the .net have any editorial links from
trusted sources that you could get to switch over to the .co.uk? This is not the same as going back to the usual suspects (ie, to the kinds of links that got you into trouble in the first place). Avoid any chance of carrying over some of the tainted legacy. Make sure that your new links are clean, and that you don't build them unnaturally. A temptation will be to build them too fast.
As far as Google's view as a registrar, I don't think they're eager to create a vast wasteland of derelict domains. That would be bad for the health of the web, and they know it.
In another current thread here, buckworks notes some comments she heard Matt Cutts make about Google's view of domain health and of moving ahead rather than looking back....
Matt said that they try to evaluate a site based on what it is now rather than what it might have been in the past.
To a degree, it makes me wonder whether your domain change is necessary, but it might make sense.
Several comments in that thread relate to your concerns here. The big difference, I think, is that you're trying to maintain brand identity (at least the good parts of it), whereas on the other thread, brand identity would have to be changed. See...
Is buying a previously owned domain name still dangerous? http://www.webmasterworld.com/google/4515322.htm [webmasterworld.com]
Another option for you, as I suggest with that domain purchase, might be heavy use of the disavow tool. That's not something I'd recommend for most sites unless they know what they're doing and very carefully evaluate what they're disavowing.
Changing domains is an equally big move, albeit in a way it does seem clearer.