Well, ViperCE, don't take this as insulting but, are you sure you input the allowable soil bearing pressure in the correct units? Are you sure the program is using the same units to calculate the footing area? ie, allowable soil in N/m^2 but loads in kN.
Staad is not the best at handling units, particularly when the normal units change from loading (kN) to resistance (N/m^2). At least when working in Imperial units, this problem comes up a lot. Loads in kips, but soil resistance in psf, and soil subgrade modulus in kip/in^3. If not very careful, a simple units error can obviously throw the results out the window.
I always double and triple check the data input, because, as the saying goes, "...garbage in = garbage out".