For the table use:
default charset = utf8 collate utf8_general_ci
then change the charset of the form sending the data:
<form accept-charset="utf8" action="" method="post">
and it should work fine. If this is not enough then change the configuration of Apache by adding:
AddDefaultCharset UTF-8
More information: http://httpd.apache.org/docs/2.2/mod/core.html#adddefaultcharset
EDIT
Wondering: the problem is related only to PHPMyAdmin? Could be your browser encoding.