What if interaction wipes out my direct effects in regression? In a regression, the interaction term wipes out both related direct effects. Do I drop the interaction or report the outcome? The interaction was not part of the original hypothesis. 
 A: This may be a problem of interpretation, a misunderstanding of what a so-called "direct effect" coefficient really is.
In regression models with continuous predictor variables and no interaction terms -- that is, with no terms that are constructed as the product of other terms -- each variable's coefficient is the slope of the regression surface in the direction of that variable. It is constant, regardless of the values of the variables, and is obviously a measure of the effect of that variable.
In models with interactions -- that is, with terms that are constructed as the products of other terms -- that interpretation can be made without further qualification only for variables that are not involved in any interactions. The coefficient of a variable that is involved in interactions is the slope of the regression surface in the direction of that variable when the values of all the variables that interact with the variable in question are zero, and the significance test of the coefficient refers to the slope of the regression surface only in that region of the predictor space. Since there is no requirement that there actually be data in that region of the space, the apparent direct effect coefficient may bear little resemblance to the slope of the regression surface in the region of the predictor space where data were actually observed. There is no true "direct effect" in such cases; the best substitute is probably the "average effect": the slope of the regression surface in the direction of the variable in question, taken at each data point and averaged over all data points. For more on this, see Why could centering independent variables change the main effects with moderation?
A: In a regular multiple regression with two quantitative predictor variables, including their interaction just means including their observation-wise product as an additional predictor variable: $Y = \beta_0 + \beta_1 X_1 + \beta_2 X_2 + \beta_3 (X_1 \cdot X_2) = (b_0 + b_2 X_2) + (b_1 + b_3 X_2) X_1$
This typically introduces high multicollinearity since the product will strongly correlate with both original variables. With multicollinearity, individual parameter estimates depend strongly on which other variables are considered - like in your case. As a counter-measure, centering the variables often reduces multicollinearity when the interaction is considered.
I'm not sure if this directly applies to your case since you seem to have categorical predictors but use the term "regression" instead of "ANOVA". Of course the latter case is essentially the same model, but only after choosing the contrast coding scheme as Ben explained.
A: I think this one is tricky; as you hint, there's 'moral hazard' here: if you hadn't looked at the interaction at all, you'd be free and clear, but now that you have there is a suspicion of data-dredging if you drop it.
The key is probably a change in the meaning of your effects when you go from the main-effects-only to the interaction model. What you get for the 'main effects' depends very much on how your treatments and contrasts are coded. In R, the default is treatment contrasts with the first factor levels (the ones with the first names in alphabetical order unless you have gone out of your way to code them differently) as the baseline levels.
Say (for simplicity) that you have two levels, 'control' and 'trt', for each factor. Without the interaction, the meaning of the 'v1.trt' parameter (assuming treatment contrasts as is the default in R) is "average difference between 'v1.control' and 'v1.trt' group"; the meaning of the 'v2.trt' parameter is "average difference between 'v2.control' and 'v2.trt'".
With the interaction, 'v1.trt' is the average difference between 'v1.control' and 'v1.trt' in the 'v2.control' group, and similarly 'v2.trt' is the average difference between v2 groups in the 'v1.control' group. Thus, if you have fairly small treatment effects in each of the control groups, but a large effect in the treatment groups, you could easily see what you're seeing.
The only way I can see this happening without a significant interaction term, however, is if all the effects are fairly weak (so that what you really mean by "the effect disappeared" is that you went from p=0.06 to p=0.04, across the magic significance line).
Another possibility is that you are 'using up too many degrees of freedom' -- that is, the parameter estimates don't actually change that much, but the residual error term is sufficiently inflated by having to estimate another 4 [ = (2-1)*(5-1)] parameters that your significant terms become non-significant. Again, I would only expect this with a small data set/relatively weak effects.
One possible solution is to move to sum contrasts, although this is also delicate -- you have to be convinced that 'average effect' is meaningful in your case. The very best thing is to plot your data and to look at the coefficients and understand what's happening in terms of the estimated parameters.
Hope that helps.
A: Are you sure the variables have been appropriately expressed?  Consider two independent variables $X_1$ and $X_2$.  The problem statement asserts that you are getting a good fit in the form
$$Y = \beta_0 + \beta_{12} X_1 X_2 + \epsilon$$
If there is some evidence that the variance of the residuals increases with $Y$, then a better model uses multiplicative error, of which one form is
$$Y = \beta_0 + \left( \beta_{12} X_1 X_2 \right) \delta$$
This can be rewritten
$$\log(Y - \beta_0) = \log(\beta_{12}) + \log(X_1) + \log(X_2) + \log(\delta);$$
that is, if you re-express your variables in the form
$$\eqalign{
\eta =& \log(Y - \beta_0) \cr
\xi_1 =& \log(X_1)\cr
\xi_2 =& \log(X_2)\cr
\zeta =& \log(\delta) \sim N(0, \sigma^2)
}$$
then the model is linear and likely has homoscedastic residuals:
$$\eta = \gamma_0 + \gamma_1 \xi_1 + \gamma_2 \xi_2 + \zeta,$$
and it may just so happen that $\gamma_1$ and $\gamma_2$ are both close to 1.
The value of $\beta_0$ can be discovered through standard methods of exploratory data analysis or, sometimes, is indicated by the nature of the variable.  (For instance, it might be a theoretical minimum value attainable by $Y$.)
Alternatively, suppose $\beta_0$ is positive and sizable (within the context of the data) but $\sqrt{\beta_0}$ is inconsequentially small.  Then the original fit can be re-expressed as
$$Y = (\theta_1 + X_1) (\theta_2 + X_2) + \epsilon$$
where $\theta_1 \theta_2 = \beta_0$ and both $\theta_1$ and $\theta_2$ are small.  Here, the missing cross terms $\theta_1 X_2$ and $\theta_2 X_1$ are presumed small enough to be subsumed within the error term $\epsilon$.  Again, assuming a multiplicative error and taking logarithms gives a model with only direct effects and no interaction.
This analysis shows how it is possible--even likely in some applications--to have a model in which the only effects appear to be interactions.  This arises when the variables (independent, dependent, or both) are presented to you in an unsuitable form and their logarithms are a more effective target for modeling.  The distributions of the variables and of the initial residuals provide the clues needed to determine whether this may be the case: skewed distributions of the variables and heteroscedasticity of the residuals (specifically, having variances roughly proportional to the predicted values) are the indicators.
