Thanks for the welcomes...and I understand that there are some problems with sexing yellow labs, but as you elude to Dawn, observation, over time, can make things pretty clear. IME though, my males were always rather easy to pick out of a crowd due to a larger/more 'bold' black stripe on the dorsal fin...but again, that is just my experience with them. And in case I wasn't as clear as I should have been, I wasn't trying to say that only one male yellow lab should be kept per tank as might be the advice given for other mbuna, but only that more females than males should be kept; whether than be one male/three females, two males/five females, etc...etc...etc...
I also agree that, in theory, if fishless cycling, there is less risk with adding higher numbers of fish at one time -- but IMHO, it is still always best to go slow...which is probably even more true when stocking with cichlids since, in this case, there is some strategy to which species of fish to add first and all of that. Personally, other than that one instance of having an overly dominant yellow lab (versus other yellow lab males anyways), I have found that stocking the least aggressive cichlid first - hence, allowing them to establish territories and a hierarchy before adding other fish which may be somewhat faster or more determined to do so can save some headaches in the long run...but would add to that a trick that has helped me out a number of times in that, each time you add a new group of fish, do some quick rearranging in the tank to 'bust up' any strongly held territories and sort of confuse your fish a little bit. Additionally, if you want to use dither fish of any sort, those are almost always best added first IMHO and IME.
Another hint that I would strongly suggest you consider fully, especially if you are going to use the cichlid substrate shown on the web page you gave a link for, is to go above and beyond the often suggested acclimation procedures of simply floating the bag until water temps match by using a drip acclimation (or equivalent...I can't say I have ever used the entire drip method, but simply add small amounts of water to the bag over a period of time...even with my saltwater fish) technique to allow your new cichlids (and/or dither fish) time to adjust from the LFS's water chemistry to yours - which would almost certainly be different unless they are using the same substrate and water source (e.g. same city water...and even then, differences can occur). As I brought up before, many of the cichlids you would find on a regular basis, unless labeled otherwise, are tank bred and hence, may have never experienced the sort of water chemistry the substrate you are thinking of would create. While it is very true that I have never used that substrate before so I can't say how good or bad it is, the point is that these differences between an LFS's tank and ours can be dramatic, to say the least. Always best to 'play it safe' IMHO!
Conversely, if you do go with sand, there is really no problem with doing so (assuming that it is an aquarium safe version) and any issues/concerns over doing so can be overcome with proper acclimation techniques anyways...which is my opinion, but based upon some rather strong scientific facts (for those naysayers out there...

). Personally, I love sand as a substrate and it works relatively well with mbuna who, as already mentioned, will dig in it - primarily when they want to mate I believe, but I could be wrong on that. Point being, if they want to dig, sand seems like the much easier option for us as hobbyists because we can simply push it back in place with any number of tools, including a net.
Regarding the crushed coral, if you really feel compelled to use it, there is nothing wrong with that....although you really don't have to. Honestly, I cannot think of any cichlid other than discus and
maybe angelfish which would refuse to breed or behave any different when kept in water with a differing pH than it would find in nature...and to be honest, it can be a little bit risky for us to 'tinker' too much with pH since, if changes are made too fast or too large, our fish can be faced with osmotic shock issues - which can lead not only to illnesses/diseases, but just as easily death (which is also why I feel we should do more than 'float the bag til temps match and release our fish'). Granted, crushed coral and similar substrates are much longer lasting than most, if not all of the buffering chemicals and/or products available today, but it is not a permanent solution and over time, dissolves into the very same water we are replacing during water changes - hence, it becomes less and less effective, albeit very slowly. My thinking here is simply this: Why become a 'slave' to a product or procedure that we, and our fish, really could do without? (Again, just my opinion, and I am sure others will disagree...which is fine with me)
Lastly...don't be too hasty with starting completely over!!! That substrate you want to change, including all of that great (and established) filter media it sounds you are planning on throwing out can be your very best friend right now - especially if you are going to fishless cycle the tank since it may severely reduce the amount of time between now and when you can start adding your new aquatic friends!!! While you don't have to, of course, I would place some of that substrate (probably as much as possible even) in a filter sack or even a clean, unscented nylon stocking and keep it in the tank until you have made your changes and are re-cycled. This would completely negate the need for you to wait for the beneficial bacteria to find your tank (it will come on its own, again, for those naysayers out there...millions of people use the good old 'wait and see' method) OR, even better, save you some money on buying those bacteria-based products which, depending on how they are stored and cared for before you buy them (which, I might add, is out of our control, as well as being impossible to verify 100% accurately), may or may not work (...bought a 'bad' package of BioSpira once - it was a mess that I would love to forget about!!!). The best part is, since you have kept it in a bag of some sort, you can remove it once your tank is up and ready (read: safe) for aquatic life again so that it doesn't 'clash' with your new aqua-scaping. You can also do the same with your filter media...to include any older carbon filter media since beneficial bacteria also populate that area to some extent as well (depending on how long it has been since you last replaced it obviously...it is, more or less, just carbon gravel in most cases).
Oh, and one more thing you might be interested in, (sorry to go on and on...as you can tell, I love to 'talk fish') especially if you go with the sand substrate, check into the benefits of using a substrate cable heater - like the one you can see by clicking
HERE - since these can help reduce the problems associated with anaerobic pockets being formed in sand and basically creates much of the same advantages as an under-gravel filter, without the problematic maintenance issues associated with them.