I'm not exactly sure what you are asking, but here are some thoughts.
Does the shapefile you are using have a defined coordinate system? You first have to define a geographic coordinate system and then project the shapefile. Projecting a shapefile that doesn't have a defined coordinate system causes mumbo-jumbo.
Are you using a downloaded or a self-generated shapefile? E.g. Tiger/Line Census files come with a pre-defined coordinate system (NAD 1983, I believe), but are not projected.
The "Define Projection" and the "Project" tools will be helpful in achieving your goals.
I understand the 2 step process. I have contacted a GIS help desk and they are having trouble, as well. A suggestion was to contact the person who sent me the files, which I have done. Will find out more on that late next week. A thought was that the data were collected under an unknown coordinate system by mistake.
When I "define projection" a check mark comes up on the lower right corner signifying the process was successful. When I "project" a little x comes up where a check mark should be. This tells me that the process was unsuccessful. I was planning to look into this error code to see where the problems could arise.