After numerous unsuccessful attempts to contact the Microsoft UDDI team I emailed Karsten Januszewski directly and he managed to get it fixed in less than a day. Thanks Karsten!
We are now at level 2, so we can publish whatever we want. Currently we have seven services and this weblog registered.
What's interesting is that the UDDI categorization scheme seems to have changed. One can now do a successful search in InfoPath/VS.NET only if a service is assigned to wsdlSpec category.