For our use case we need to be able create Custom Objects (metadata) on the fly, possibly copied from a template object then modified.

How would I go about this, and are there any examples out there?

I've already seen this other thread:

http://boards.developerforce.com/t5/Apex-Code-Development/Is-it-possible-to-call-Metadata-API-from-Apex-code-Getting-Error/td-p/119412

I haven't been able to implement this though.   I've exported the WSDL, converted it to apex, and put it into a class via the Force IDE.  The class saves/compiles, but I've been unable to actually write any apex using it to do anything, as I can't find any examples and I am not clear on what the syntax should be (though from the end of the thread it appears they were not successful either?).

Has anyone done this successfully?  I actually see that there has been a related contest put up at http://blogs.developerforce.com/developer-relations/2012/01/developer-content-contest-2-metadata-api.html but I need to figure out if what I need is possible quickly since whether/how we use salesforce hinges on this