a 4GB indexed database containing one table with about a million rows

Is it possible the hard drive on the problem machine is formatted using a FAT/FAT32 partition? If so you may be coming up against the 4GB file size limit.