I ended up using:

• System Language
• Platform Type
• Time Stamp
• Running Time
• Random Number

So for the same ID to be generated two of the same device with the same language setting would have to open the game at the exact same time and the devices would both have to request the ID at the exact same time, then both devices would have to generate the same random number.

    public static string GetUniqueID(){
       string key = "ID";

       var random = new System.Random();              
       DateTime epochStart = new System.DateTime(1970, 1, 1, 8, 0, 0, System.DateTimeKind.Utc);
       double timestamp = (System.DateTime.UtcNow - epochStart).TotalSeconds;

       string uniqueID = Application.systemLanguage                 //Language
          +"-"+GetPlatform()                           //Device   
          +"-"+String.Format("{0:X}", Convert.ToInt32(timestamp))          //Time
          +"-"+String.Format("{0:X}", Convert.ToInt32(Time.time*1000000))     //Time in game
          +"-"+String.Format("{0:X}", random.Next(1000000000));          //random number

       Debug.Log("Generated Unique ID: "+uniqueID);

       if(PlayerPrefs.HasKey(key)){
         uniqueID = PlayerPrefs.GetString(key);      
       } else {       
         PlayerPrefs.SetString(key, uniqueID);
         PlayerPrefs.Save();  
       }

       return uniqueID;
    }

If System.GUID.newGUID() crashes the environment, I would be tempted to raise that as a software defect as that is what should, in principle, be used. However, if that were not available, consider using a low level timestamp (say ... seconds since Jan 1st 1970). You can get away with this is the ID doesn't have to be guaranteed to be "globally" or "universally" unique.

According to the Mono Compatibility page the Guid class is fully supported on all platforms / Mono versions. Stripping shouldn't be an issue unless you use the micro mscorlib. Are you sure you spelled it correct?

It's:

System.Guid.NewGuid();

So in C# you would do something like:

System.Guid myGUID = System.Guid.NewGuid();

edit
Like poday mentioned, if you use the micro mscorlib the Guid class is not included and you have to use a custom way to build a pseudo Guid.