Even very weak nonzero effects will become statistically significant if you have enough data. A significant F test simply means that the proportion of variance explained is larger than would be expected if there was no effect at all, i.e., it is a statement about relative effect strength. It does not mean that the effect is large in absolute terms. You can investigate this by simulating data with a weak effect and progressively larger sample sizes.
Thus, your interpretation is not correct:
I believe that this result would suggest that I am missing an especially important independent variable or that the relationship is not linear.
As an example, I simulated a dataset with 10,000 points, one numerical predictor, a factor with two possible levels, a straightforward two-way interaction and a tiny effect size. Here are the simulated responses against the predictor, color-coded by the factor. I am also including the fit. (The fit for group B is hard to see, it's a bit above the one for group A.)

An F test on the correctly specified model gives us a "highly significant" result, $F(3,9996) = 29.03$, $p<2.2\times 10^{-16}$... but we only have $R^2=0.0086$, $R^2_{\text{adj}}=0.0083$.
This illustrates that a large sample size (and $n=10,000$ is large for inferential statistics) will make even a trivially weak effect (witness the $R^2$ - our model explains less than 1% of the variation) statistically significant.
R code:
nn <- 1e4
set.seed(1)
predictor <- runif(nn)
group <- as.factor(c(rep("A",nn/2),rep("B",nn/2)))
response <- 42+0.1*predictor*0.1+1*(group=="B")-
0.04*(group=="B")*predictor+rnorm(nn,0,5)
model <- lm(response~group*predictor)
summary(model)
colors <- structure(c("red","green"),.Names=c("A","B"))
plot(predictor,response,col=colors[group],pch=19,cex=0.5,las=1)
xx <- seq(0,1,by=0.1)
lines(xx,predict(model,newdata=data.frame(group="A",predictor=xx)),
col=colors["A"],lwd=2)
lines(xx,predict(model,newdata=data.frame(group="B",predictor=xx)),
col=colors["B"],lwd=2)
legend("topleft",pch=19,lwd=2,col=colors,
legend=c("A","B"),bg="white")