Sanghoon,
this message comes from resource file embedded into assembly
microsoft.office.server.search.intl.dll
and for Core Results web part this message renders when Query Error occurs instead of displaying actual search result, this is why for message XSLT customization could not be applied as for regular search results.
But it could be customized on the client side, for example the script below (jQuery is used here) changes this message:
$(function()
{
var srchErrorLabel = $('.srch-wperror').find('span');
srchErrorLabel.text('Place user friendly message here');
})
So, if you add on page where Core Results web part is located this script, the message
Place user friendly message here
will be displayed.
Hope this helps,
Vadim