OK, I figured out one of the problems. It turns out I had been given a grid that went from +120 (west coast US) to +292 (western Australia). I was told it was wgs 84. Anyway, I managed to use the shift command under projections & transformations/raster to get the data shifted -360°. I then tried to define the projection again. It work failry fast this time, however the properties did not show the projection. I did this twice with no projection showing up in the properties window. If I look at it in arcmap/arccatalog there is no projection defined. However, if I open up traditional arccatalog, the projection is defined. I attached screen grabs for your information. If I look at the grid directory I see the prj.adf which is defined correctly.
Next I tried changing the projection of the data frame, and indeed the grid cannot project on the fly. Then I tried adding the grid from traditional ArcCatalog to the data frame. It gave me a warning about the data lacking a projection. When I removed the layer and added it again, no error appeared, however it still could not project on the fly. Do you think this is happening because my data goes 0 to -360 instead of +-180? My data also crossed the 180° line. It is about 500 MB in zip format.
Next I went to 9.3.1 arcmap. It sees the projection in the properties window, but cannot project on the fly. If I set the data frame to wgs84, my vector data lies over the grid correctly, except for that which crosses 180° which is on the other side of the screen.
So, my problem is figuring out how to get the data in a projection arcmap will recognize. Your problem may be the properties display difference between arccatalog stand-alone and arcmap as the projection information is present in the grid.
