Looking for a bottleneck in MySQL server

I have two Ubuntu servers with very similar, if not identical, configuration: both have 16 cores (4 E5540 Xeons), 16GB RAM, HP Smart Array P212 controllers with 2 HDDs in RAID1. I/O scheduler used is deadline. Both run the same versions of MySQL (5.1.26, later upgraded to 5.1.47/Percona Server 10.2). The databases are similar, but not exactly the same. MySQL configuration is also very similar. But the performance is incomparable:

Server1:

mysql> alter table documents add column test int(10) unsigned not null default '0';
Query OK, 2496892 rows affected (7 min 18.41 sec)
Records: 2496892  Duplicates: 0  Warnings: 0

mysql> alter table documents add column test int(10) unsigned not null default '0';
Query OK, 2497414 rows affected (1 min 59.15 sec)
Records: 2497414  Duplicates: 0  Warnings: 0

Server2 is 3.7 times as fast.

MySQL benchmark (sql-bench) only confirms that Server2 is much faster:

Server1:

alter-table: Total time:  7 wallclock secs 
ATIS: Total time:  3 wallclock secs 
big-tables: Total time:  0 wallclock secs
connect: Total time:  1 wallclock secs 
create: Total time:  7 wallclock secs 
insert: Total time:  3 wallclock secs
select: Total time:  2 wallclock secs 
wisconsin: Total time:  4 wallclock secs 

alter-table: Total time:  1 wallclock secs 
ATIS: Total time:  1 wallclock secs 
big-tables: Total time:  0 wallclock secs 
connect: Total time:  0 wallclock secs 
create: Total time:  0 wallclock secs 
insert: Total time:  2 wallclock secs 
select: Total time:  2 wallclock secs
wisconsin: Total time:  2 wallclock secs 

The only difference between the servers is the OS version. Server1 is Ubuntu 9.10 with 2.6.31-20-server #58-Ubuntu SMP kernel, while Server2 is Ubuntu 10.05 with 2.6.32-22-server #33-Ubuntu SMP.

I had serious suspicions about I/O on Server1. So, iostat -dkx gives significantly higher %util values on Server1, about 25-30% vs 1% on Server2.

I ran I/O benchmarks (iozone3), but to my surprise, Server1 produced slightly better results. RAM test with mbw was also in favor of Server1.

What should I test next? What could be the problem?

Thank you.