OK, we resolved our issue about a week ago, but we’ve been too busy implementing the results for me to follow-up with the answer.  Since there seems to be a frustrating amount of unanswered Salesforce threads, I wanted to take a moment to follow-up on this thread.

First, we have been running a parallel thread at:
http://salesforce.stackexchange.com/questions/36846/metadata-api-custom-field-permissions
 

We wouldn’t have solved our problem without the assistance of sfdcfox on the other thread, and the blogs offered by Terry Luschen (So, Thank you to both of you!).  Here are the Blogs from Terry that we found helpful (they are in vb.net, but could easily be converted to C#):

Retrieve:  http://www.sundoginteractive.com/sunblog/posts/calling-retrieve-from-the-metadata-api-in-vb.net
Deploy: http://www.sundoginteractive.com/sunblog/posts/calling-the-salesforce-metadata-api-from-vb.net

Basically, we moved away from building the custom fields and permissions in pure code and switched to using xml deploys.  The code version required us to batch up our custom fields in groups of 10 and then to submit those with a “create” statement (see our earlier note).  This worked, but then we couldn’t figure out how to submit the proper permissions (now that we have the xml profiles working, maybe we could try to emulate the profile file in code, but the xml version is the better solution for us).  The xml deploy approach allowed us to batch all of our custom fields requirements together (we were adding 40+ fields to Accounts and 10+ fields to Contacts), along with the profiles and submit them with a single deploy.

Next it took us a while to figure out the structure of the deployment package.  The Metadata documentation has a lot of great information, but it is also lacking in how to bundle everything together for a finished solution.  It wasn’t until we read the blog from Terry Luschen for performing a deploy from code, and we combined that information with running his code for retrieving the zip package that we figured this out.  By retrieving a package, we were able to see the directory structure and file names that the zip file required.  (Note:  We didn’t download the .Net zip packages that Terry suggests, since we weren’t dynamically building the zip package.  We zipped and unzipped locally on our development machine, but I strongly recommend performing a retrieve to see the proper structure.)

Here are the actual steps we took to build our deploy file:

1.)  We created a Directory we titled “DeployFiles”
2.)  Within the DeployFiles directory we created a directory titled “objects”
3.)  In the objects directory we created our custom field files.  The key was to name the files appropriately:

The account fields were in a file named “Account.object” and the structure looked like this:

<?xml version="1.0" encoding="utf-8"?>
<CustomObject xmlns="http://soap.sforce.com/2006/04/metadata">
 <deploymentStatus>Deployed</deploymentStatus>
 <description>Setup Custom Fields for Account Standard Object</description>
 <fields>
  <fullName>AccountTestField1__c</fullName>
  <description>Account Test Field 1</description>
  <inlineHelpText>Account Test Field 1</inlineHelpText>
  <label>Account Field 1</label>
  <type>Text</type>
  <length>10</length>
 </fields>
 <fields>
  <fullName>AccountTestField2__c</fullName>
  <description>Account Test Field 2</description>
  <inlineHelpText>Account Test Field 2</inlineHelpText>
  <label>Account Field 2</label>
  <type>Text</type>
  <length>20</length>
 </fields> 
</CustomObject>

The contact fields were in a file named “Contact.object” and the structure looked like this:

<?xml version="1.0" encoding="utf-8"?>
<CustomObject xmlns="http://soap.sforce.com/2006/04/metadata">
 <deploymentStatus>Deployed</deploymentStatus>
 <description>Setup Custom Fields for Contact Standard Object</description>
 <fields>
  <fullName>ContactTestField1__c</fullName>
  <description>Contact Test Field 1</description>
  <inlineHelpText>Contact Test Field 1</inlineHelpText>
  <label>Contact Field 1</label>
  <type>Text</type>
  <length>10</length>
 </fields>
 <fields>
  <fullName>ContactTestField2__c</fullName>
  <description>Contact Test Field 2</description>
  <inlineHelpText>Contact Test Field 2</inlineHelpText>
  <label>Contact Field 2</label>
  <type>Text</type>
  <length>20</length>
 </fields> 
</CustomObject>

4.)  Next we created a directory in the DeployFiles directory titled “profiles”
5.)  In the profiles directory we created two files (we’re not sure if we only needed one of these, or if there should be more profile files, but it seems to be doing the job for us so far).  Both files had the exact same content, but the different file names are important:

The admin (System Admin) permissions were placed in a file named “Admin.profile” and the Standard User permissions were placed in a file named "Standard.profile".  Both files had the same content:

<?xml version="1.0" encoding="utf-8"?>
<Profile xmlns="http://soap.sforce.com/2006/04/metadata">
 <userPermissions>
  <enabled>true</enabled>
  <name>ApiEnabled</name>
 </userPermissions>
 <fieldPermissions>
  <field>Account.AccountTestField1__c</field>
  <editable>true</editable>
  <hidden>false</hidden>
  <readable>true</readable>
 </fieldPermissions>
 <fieldPermissions>
  <field>Account.AccountTestField2__c</field>
  <editable>true</editable>
  <hidden>false</hidden>
  <readable>true</readable>
 </fieldPermissions> 
 <fieldPermissions>
  <field>Contact.ContactTestField1__c</field>
  <editable>true</editable>
  <hidden>false</hidden>
  <readable>true</readable>
 </fieldPermissions>
 <fieldPermissions>
  <field>Contact.ContactTestField2__c</field>
  <editable>true</editable>
  <hidden>false</hidden>
  <readable>true</readable>
 </fieldPermissions>
</Profile>

6.)  Finally, we created the "package.xml" file and placed it in the DeployFiles directory.  It looked like this:

<?xml version="1.0" encoding="utf-8"?>
<Package xmlns="http://soap.sforce.com/2006/04/metadata">
 <types>
  <members>Account.AccountTestField1__c</members>
  <members>Account.AccountTestField2__c</members>
  <members>Contact.ContactTestField1__c</members>
  <members>Contact.ContactTestField2__c</members> 
  <name>CustomField</name>
 </types>
 <types>
  <members>Admin</members>
  <members>Standard</members>
  <name>Profile</name>
 </types>
 <version>29.0</version>
</Package>

7.)  Now the DeployFiles Directory structure looked like this:

          DeployFiles
              package.xml
              objects
                  Account.object
                  Contact.object
               profiles
                   Admin.profile
                   Standard.profile

8.) Then we zipped the DeployFiles directory in to a .zip file and added it to our project (in Visual Studio we placed it in App_Data).
9.)  Here's a subset of the code we used to deploy the file (See links from Terry above for more details and "waitUntilDone" routine):

' Initalize MetaService
' Login to MetaData Service (For Managing Fields)
myMetaService = New sfMetadata.MetadataService
myMetaService.Url = myLoginResult.metadataServerUrl
myMetaService.SessionHeaderValue = New sfMetadata.SessionHeader
myMetaService.SessionHeaderValue.sessionId = myLoginResult.sessionId.ToString

' Set up Deploy Options
deployOpts.runAllTests = False
deployOpts.runTests = Nothing
deployOpts.autoUpdatePackage = False
deployOpts.allowMissingFiles = False
deployOpts.checkOnly = False
deployOpts.ignoreWarnings = False
deployOpts.performRetrieve = False
deployOpts.purgeOnDelete = False
deployOpts.rollbackOnError = True
deployOpts.singlePackage = False

' Get the Packaged Zip File Path
strAppDataPath = GetAppDataPath()
strZipFullPath = strAppDataPath & "DeployFiles.zip"

' Verify Zip file exists
If System.IO.File.Exists(strZipFullPath) Then

' Load the Zip File
byteFile = LoadFile(strZipFullPath)
' Deploy the Package
asyncResultItem = myMetaService.deploy(byteFile, deployOpts)

' Wait Until Done
If asyncResultItem.done = False Then
 waitUntilDone(asyncResultItem.id)
End If

' Get Deploy Result
newDeployResult = myMetaService.checkDeployStatus(asyncResultItem.id, True)
If newDeployResult.success Then
 strResult = "Complete"
Else
 { Handle Errors }
End If

10.)  It took us a while to debug our routines and set the appropriate Deploy Options.  Originally we weren't receiving any errors other than "Payload Error", but once we got the structure close to what we needed, the error messages started becoming more useful.  There is no guarentee that we have all of these files right, and you'll need to adjust them for your needs, but hopefully the documentation can be of assistance.  One note we learned from sfdcfox was that you can all check for Deploy Errors by logging into Salesforce and going to Setup > Deploy > Deploy Status.

This solution is working for us so far and hopefully this information will be helpful to you.  We still have some outstanding issues we need to address:

    - It appears that Salesforce limits the Professional Edition functionality (unless you call and can talk the rep into enabling API's?), so our clients will need Enterprise Edition or above.  We're trying to learn more about this now.
   -  Also, we're using the SOAP API for populating the Custom Fields we've created with data.  So now we're concerned about Salesforce quantity limits and not sure if that will become an issue for us down the road.

Any tidbits or suggestions associated with those two issues is greatly appreciated.