An excellent blog post by Contrast today covered change requests for web applications. While the example used in the blog post may be a little overdrawn, the main point excellent: there are no small changes to web applications.
Magento’s very wide range of out of the box features can lead you to think additional features are built upon the existing framework very quickly and easily. The architecture of Magento is solid of course but most of the time the issue with changes is not solely the technical implementation but also defining what has to be built. It helps to realize that Magento took 57 man years to design & develop
A good Magento implementation partner should ask questions and describe what is going to be built and changed before actually diving into the graphical and technical details. Especially in Magento Enterprise Edition projects, document as much as possible!