I don't know of a way to change the error message. The other alternative is to use Visual Basic for Application (VBA) code to check the values prior to them being entered into the table. I believe that the code would go in the before update event of the form that you are using for data entry. The code might go something like this (air code, not tested)
Code:
If Dcount("*", "YourTableNameHere","field1=" & me.ControlName1 & " AND Field2=" & me.controlName2)>0 THEN
msgbox "The values you entered already exist"
'you will have to have some code here to clear the controls or to move the user to the record that already exists
End if