I flew with Avex at Midrand back in April this year. They are a small outfit but recommended by a South African who learnt there.
The Flight Training College you mentioned looked a nice set up, with a smart newish building etc. Good fun taxxing out when 5500' up!
One thing I was impressed with was the fact that there is no LARS as such, just a common freq where people make blind calls of a/c type, level, position and direction. Sure aids your nav skills and location awareness!
The only problem with the cheap price at Avex etc, is really old aircraft. I flew in an old PA28-140 (possibly construction number 001!!) which felt a little underpowered.
Another option is Lanseria airport on the other side of Jo'burg - a big bizjet/charter centre (similar to Luton but more redeveloped)
Enjoy either way......
AM