Hi Mark,
When you can see your new output in your geoprocessing results window, are you able to right-click it and "add to display" or "copy location"? Paste the location into a text file - is it where you expect it to be?
When you say "I can't add it to my map," do you mean you get an error, or does nothing happen and your new feature class doesn't appear in your table of contents?
Changing the default geodatabase to your desired output location can also help to keep you from inadvertently saving to an incorrect directory when you run the tool.
Let us know how you go.
Cheers
Liz