I always thought it came from lapis lazuli (portuguese). Azul as a subpar of Lazuli even sounds exactly the same in portuguese.