The tar command removes the leading slash, so that the paths in the tar file are relative paths. This is for safety reasons.
This means that the verification stage may be unable to find the original files. Because it is using the relative paths it finds in the tar file, it will only be able to find the original files if your current directory is the root directory (so it gives the warning "Verification may fail to locate original files").
This happened in your case, because your current directory was not root (so you received a stat error, which means the verification failed). If you want to get rid of the warnings, you would need to do something like this:
Code:
cd /
tar cfW /media/example.tar home
If you leave the slash at the start of home, you will get warnings, but the verification at least will succeed.