I really advice you not to take the bus - there are very hard roads in Kazakhstan, and buses not in good condition.
If you want, try the Hitchhiking - Novosibirsk, Barnaul, Rubtsovsk, Veselojarsk -Aul (border point here), Semipalatinsk (Semey), Georgievka, Ayagoz, Taldykorgan, Almaty.
This will be not very quick, but more comfortable.
Also I found a flight not by S7: Investavia opens new flight from Almaty to Novosibirsk, and it will be tomorrow, Friday, at 13-45:
- Almaty to Novosibirsk: #TL1025, departure at 13-45, arrival at 16.55, each Friday, from Jully, 08, 2011 to September, 02, 2011, model Fokker 100
- Almaty to Novosibirsk: #TL1025, departure at 13-05, arrival at 16.10, each Monday, from Jully, 11, 2011 to August, 29, 2011, model Fokker 100
Price is from 30000 for one person, time in air: 2 hours 10 minutes Number of places: 8 - business class, 90 - economy class. Phones for help:
+7-727-2798686, 2790952, 2790637, 2731313
Update: InvestAvia is banned in EU because of safety :-(