Creating a legend for a dendrogram with coloured leaves in r

I have coloured the leaves in a dendrogram as follows

require(graphics)

dm <- hclust(dist(USArrests[1:5,]), "ave")

df<-data.frame("State"=c("Alabama","Alaska","Arizona","Arkansas","California"),   "Location"=c("South","North","West","South","West"))


color.sites<-function(dm){
    dend<-as.dendrogram(dm)
    plot(dend)

    cols <- attributes(dend)
    df$ColorGroups <- factor(df$Location)

    #Set colour pallette
    Location.Pal <- rainbow(nlevels(df$ColorGroups), s=0.9,v=0.9,start=0.1,end=0.9,alpha=1)

    colorleaves <- function (n) {
    # only apply to "leaves" in other words the labels
    if(is.leaf(n)) { 
        i <- which(df$State == attr(n,"label"))
        col.lab  <- Location.Pal[[unclass(df$ColorGroups[[i]])]]
        a <- attributes(n)
        attr(n, "nodePar") <- c(a$nodePar, list(lab.col = col.lab))
    }
    n
}

xx <- dendrapply(dend, colorleaves)

plot(xx, cex=3, cex.main=2, cex.lab=5, cex.axis=1, mar=c(3,3,3,3), main="Title")
}

color.sites(dm)

I would like to: 1) add a legend explaining the colours (i.e. Orange = North) 2) make the leaf labels larger and bolder (cex.lab does not seem to do the job) 3) create a color palette that has sharply contrasting colour (rainbow,heat.colors etc all seem to blend together when there are many leaves and colours in the dendrogram.

Any advice is greatly appreciated !