Yes, I made a mistake. Gaussian elimination is O(n^3), but there are general algorithms which are as fast (or slow, depending on how you look at it) as the current complexity bound for matrix multiplication which is O(n^{2.737}). Not the end of the world, I corrected the article. Reference:
http://theory.epfl.ch/vishnoi/CargeseLectures.pdf
Still, the point stands that you'd never want to actually solve a large system "the generic way" unless you really have to (i.e. you cannot identify a structure for which you have a faster algorithm).