Today i also faced the similar issue when i tried to import the webpart from Dev site and export to QA site. when i try to add this webpart to the page , it was giving the error."$Resources:core,ImportErrorMessage" . I could not figure out the solution for hours. I came to this Questions and did almost everything which has said here in other answers. like Adding the Safe control to Web config file and checking the public Key token and match with the assembly available in Webpart. but i was getting the Error again and again.
By doing try and trial once i Deployed the solution in Dev using VS 2010. and instead of Importing the .Webpart file from webpart gallery and exporting to the QA webpart gallery, i got the .webpart file from the "pkg" folder which is created by VS 2010 and then uploaded to QA webpart gallery and suddenly Error gone. you can try this if above answer does not work . it might help.
for refrence i have added same answer in my blog
http://www.spissue.com/2015/01/getting-resourcescoreimporterrormessage.html[
^]
Please let me know if anybody having objection or correction to my answer. since it was hit and trial but it worked for me so thought to share here.
Thanks.