Most commonly the default projection for GPS units is not a projection at all, but Lat lon.
You may be able to change that to the projection of your data, which would remove the message you are getting.
The other way would be to re-project your data.
After combining your shape files (if that is still what you want to do) you can simply set the projection of the document to the same projection as your default in the gps.
Then right click on the layer and select data> export.
Be sure to check the "same as data frame" check box, and select a location.
Walla! your new shape file is in the projection that the data frame is in.