ISO 27001 is unlike most (all?) other management system standards in that the Controls listed in Appendix A (and described in more detail in ISO 27002) aren't mandatory, but selected as a result of the risk assessment performed in 4.2.1 (and periodically thereafter). The controls need to be proportional to the risks identified.
(Some organizations are made to do all the controls by unthinking customers, and this makes no sense. Controls should be proportional to risks, some are not affordable, some mitigate risks that only apply to some organizations. Some - vetting staff or encryption - aren't even legal in some countries, some circumstances. Insisting on all the controls risks a false sense of security, waste of money on unnecessary controls, and installation of flimsy controls that are insufficient to withstand determined attacks.)
So, for example, having locks on doors might satisfy A.9.1.2, or might not: one only knows whether the locks are likely to be effective after risk analysis. If the risk analysis indicates that foreign intelligence services are a threat, good locks and probably several of them are advisable.
The most common reason for initial certification failures is putting controls in place (by following Appendix A or ISO 27002 mechanically) without implementing clauses 4, 5, 6, 7 and 8. The next most common cause for initial certification failure is inadequate risk assessment methodology.
One common difficulty is trying to "boil the ocean". Scope is often defined too broadly, and then the ISMS is too big to manage, and offers little value. 4.2.1.a allows an organization to focus its ISMS on the information assets that are critical to it in terms of confidentiality, integrity and availability and leave the rest to "normal" controls. For example, HR are usually good at controlling personal information and for many organizations ISO 27001 adds little value - the exceptions are those organizations (certain nameless government departments for example) whose staff might be vulnerable to coercion, in which case ISO 27001 might help protect their personal information (where they live) more effectively.
Some clients pragmatically iterate through defining scope, assessing risks, identifying controls until they narrow down on the information assets that really benefit from ISO 27001.
Especially challenging in ISO 27001 is managing behaviours of everyone in the organization, including top management. Like other management system standards, writing procedures is the easy bit - getting people to do them is another matter. For example, while a "no tailgating" policy is easy to write, getting people to do it here in the UK can be a challenge: Brits are too polite and insist on holding doors open for each other - especially when the tailgater is wearing jeans and heels, carrying a cup of hot tea in each hand and pretending to be unable to get her pass out of her pocket.
And a "clear desk" policy is sometimes greeted with "I'm too busy to do that. Lock the doors so we don't have to bother." Please note also that auditors and information security managers develop a sixth sense for where passwords are likely to have been written down ... It's important to remember too that introducing a control can itself bring risks, e.g. losing the encryption keys, backups get stolen, new automated locks lock everyone out, information security officer commits fraud (this allegedly happened at Renault), etc.
For some organizations a serious breach of information security can lead to loss of contracts, reputational damage or worse. For example, more than one company in the UK has lost Government business by mislaying a USB stick carrying large volumes of personal data, unencrypted, thus falling foul of Data Protection law. Often, breaches are caused by disgruntled employees - Wikileaks and the US diplomatic cables is the most obvious example.
This is what makes ISO 27001 an interesting challenge, and why risk assessment is essential. It's too easy to react emotionally to risks, and get controls out of proportion or even miss essentials by focusing too much on the dramatic risks reported in newspapers. The risk assessment method, leading to a sober, balanced assessment of information security risks, is an essential first step, arguably more important than the gap analysis because it will help identify where significant controls - and time and money - will be required.
Hope this helps,
Pat