Two things. First, is the lag during windows startup or in the bios startup? is the windows logo just sitting there for minutes?
Second, you had an nvidia card before, did you remove the old nvidia drivers before installing the ATi card and ATi drivers? There have always been issues when both sets are installed, this doesn't seem too far out of that realm. Best practice is to clean out all video drivers completely, then install the new ATi driver.