Here is what I did to get it fixed

Created upload and save directories

Code:

mkdir /etc/phpmyadmin/upload
mkdir /etc/phpmyadmin/save
chmod a+w /etc/phpmyadmin/upload
chmod a+w /etc/phpmyadmin/save

Edited phpmyadmin's config file
Code:

nano /etc/phpmyadmin/config.inc.php

Added the path for both upload and save directories
Code:

$cfg['UploadDir'] = '/etc/phpmyadmin/upload';
$cfg['SaveDir'] = '/etc/phpmyadmin/save';

Log out and relogin to phpmyadmin and that should do it.
In my case, I also edited php.ini to increase
Code:

post_max_size =
upload_max_filesize =

to suit my needs.

Then restarted php and nginx for new settings to take effect
Code:

 /etc/init.d/php5-fpm restart
service nginx restart