I don't think mysqlimport should be left as a "last desperate measure", and I don't see why your situation would disfavor it, so my advice would be to try that next. Any other cp1256-based tool you have that can do Arabic display should be able to show the plain-text file that you dump from the old table, to confirm that the data is okay up to that point. Then, load to and dump from the new table, and the data should be basically the same (especially if you sort it the same way from both versions).

If the data in the "fixed" table still looks buggy, you might try the following alterations to the OP code, just to see if this makes a difference (I don't know whether it will):

use Encode;  # add this near the top

my $sqlstatement = 'select name_arabic from data';
my $sth = $dbh->prepare($sqlstatement);
$sth->execute || die "Could not execute MySQL statement: $sqlstatement
+";

my @row;
my @cases; # if handling only one field, let's make this a plain array

while (@row=$sth->fetchrow_array) { # explicitly convert to utf8 (die 
+on failure)
    push @cases, decode( 'cp1256', $row[0], Encode::FB_CROAK );
}
$sth->finish();

# optimize a little: the insert statement only needs to be prepared on
+ce

$sqlstatement = 'insert into newdb.names (arabicname) values (?)';
$sth = $dbh->prepare($sqlstatement);

for my $i (0..$#cases) {  # now explicitly convert back to cp1256
    $sth->execute( encode( 'cp1256', $cases[$i] ))
         or die "putsql could not execute MySQL statement: $sqlstateme
+nt";
}
$sth->finish();
[download]

(updated to remove redundant "my" declarations on $sqlstatement and $sth)