What exactly is meant by beta dependence in this fixed bias BJT scheme?
Rearranging your formulae and using your assumptions:       


Rb = (Vcc-Ve) x (Re/Ve) x Beta. -> Rb is proportional to Beta. 


and/or, re-rearranging


Ve = (Vcc x Re)/ ( Beta x Rb  + Re) &lt;- Ve is Beta dependant. 


Beta values for a batch of transistors often differ by 2:1 and sometimes more.
Beta varies with age and temperature.
Your bias resistor and/or your operating point will be "all over the map". 

E&amp;OE - even if I made an error there (which I don't think I did) the point is that
 the circuit is "undesignable" in real world situations.