Giving this a bump, as we just had the same problem crop up -- and we've done several rebuilds. Any other options? Our error message was essentially the same:
/7/2011 9:53:35 AM Warning: Error in OpenConnectionBeginSession, HRESULT =
-2147220456 (80040418); This application has not accessed this QuickBooks
company data file before. The QuickBooks administrator must grant an application
permission to access a QuickBooks company data file for the first time.;
iContext=30