This note presents a new approach to finite-horizon guaranteed state prediction for discrete-time systems affected by bounded noise and unknown-but-bounded parameter uncertainty. Our framework handles possibly nonlinear dependence of the state-space matrices on the uncertain parameters, The main result is that a minimal confidence ellipsoid for the state, consistent with the measured output and the uncertainty description, may be recursively computed in polynomial time, using interior-point methods for convex optimization. With n states, I uncertain parameters appearing linearly in the state-space matrices, with rank-one matrix coefficients, the worst-case complexity grows as O(l(n + l)(3.5)). With unstructured uncertainty in all system matrices, the worst-case complexity reduces to O(n(3.5)).