Does an FAA pilot certificate qualify as an ICAO pilot licence?
My understanding is that most FAA licenses would also qualify as "ICAO Licenses" (certainly the ATP seems to as we have a bunch of US/FAA certificated ATPs acting as international captains for US airlines flying to/from ICAO member states). From a quick read I think anything from Private up meets the ICAO Annex 1 (personnel licensing) requirements. (It appears that ICAO charges for Annex 1, but the fine folks in the Republic of Serbia have made the 2011 edition available on their Civil Aviation Directorate's website for us to all read and enjoy).



In addition to the Annex 1 requirements, ICAO's FAQ has the following to say about licensing:


  ICAO licence or international licence
  
  ICAO does not issue any licences. Licences issued by ICAO Contracting States on the basis of Standards and Recommended Practices of Annex 1 – Personnel Licensing, are habitually called ICAO licences. This has led many to believe that there is a specific ICAO or international licence. The fact is that there is not one single international licence issued by ICAO or any other organization. States issue their own licences based on national regulations in conformity with Annex 1 specifications and validate licences issued by other Contracting States on the basis of bilateral or multilateral agreements or the fulfilment of nationally legislated requirements.


and


  International recognition of flight crew licences
  
  The Convention on International Civil Aviation, often called the Chicago Convention, provides for worldwide recognition of flight crew licences issued by any member State of the International Civil Aviation Organization (ICAO) provided that:
  
  
  the licence meets or exceeds the ICAO licensing Standards of Annex 1 – Personnel Licensing to the Convention on International Civil Aviation; and
  the licence is used on an aircraft which is registered in the State which has issued or validated the licence.
  
  
  If the licence is to be used on an aircraft which is not registered in the issuing State, the licence holder must obtain a validation of the licence from the State of Registry or alternatively obtain a new licence issued by the State of Registry. 


So basically your US/FAA license is a valid "ICAO License" as long as you're flying a US-registered aircraft &amp; the nation you're flying to/through accepts US/FAA licenses (possibly with some additional requirements on a per-country basis).

If you got a job for a Serbian airline and needed to fly an aircraft registered in Serbia you would need the Serbian Civil Aviation Directorate to issue you a license (or validate your FAA license) because they are the state of registry. 

From what I've read you can get a private license issued pretty easily in most ICAO member states - the procedures are roughly analogous to US FAR 61.75 - but if you want anything more than that there are other hoops to jump through to "convert" your license, which can range from just a written exam to a full-fledged checkride or more -- this is probably what people are referring to when they say it's difficult to get an "ICAO License" issued.