How do I change a core error message?
If that string is run through the t() function (which is probably is) and you don't want to use  String Overrides, then you can update your settings file.

For Drupal 6, putting this in your "settings.php" file should work.

$conf["locale_custom_strings_en"] = array(
  "Please Select the Valid File Format" =&gt; "The file upload field cannot upload the speicified filed",
);


In Drupal 7, you would change it to 

$conf["locale_custom_strings_en"][""] = array(
  "Please Select the Valid File Format" =&gt; "The file upload field cannot upload the speicified filed",
);


However, I am not seeing the string "Please Select the Valid File Format" in any of my D6 installs, and that is not the message I get when try to upload to a CCK filefield with the wrong file type or the MIME type doesn't match the file extension.