Reason why Update Stats with SAMPLE may take longer then with FULLSCAN
FULLSCAN is the same as SAMPLE RATE 100 with the difference that with SAMPLE RATE, SQL Server 2005 might adjust the rate up (and use a sample rate that is sufficiently high to create useful statistics) and if the requested rate creates more values than is considered needed, it “tries to match the requested sample amount”. I’m not a 100% how it is in 2005, but in 2000 it would actually revert to FULLSCAN if the sample rate exceeded some threshold (for performance). You can check which sample rate you end up with DBCC SHOWSTATISTICS… WITH STAT_HEADER.
Now Update States with SAMPLE may take longer then with FULLSCAN, the explanation to that probably lies in how samples are gathered. Thing is, when you use a sample rate, SQL Server needs to figure out an access path (heap/cl idx/non-cl idx) and it will try to find one that is NOT physically sorted on the first column in the statistics. It does this to provide a more random sample and thus more accurate statistics. For FULLSCAN, this is not an issue so the lowest cost access path is chosen.