At work we're in the process of upgrading from Office 2003 to Office 2010. The pilot users on Office 2010 were unable to edit spreadsheets on a network location while the Office 2003 users chugged right along. After a few days of troubleshooting we finally found the solution.
In order to edit files in Office 2010 the user must have Delete permissions for the folder with the document. For Office 2003 they simply required Update permissions. Hopefully our pain can be your gain.