You mean that the new entry doesn't appear under the dropdown arrow?

If yes, then there is a limit of 1000 unique entries that will appear under that
dropdown (at least in xl2003 and earlier).

Another problem could be that if you updated the entry by adding a new row, then
that row may not be part of the autofilter range.

If you filter by a different value, do you still see the new entry at the bottom
of the range?  Is the row number for that new entry still gray--not blue like
the other filtered data?

If yes, then your autofilter isn't including that row.  I'd remove the filter
and reapply it to the whole range.  

I select the range myself.  I don't let excel guess at the range to be filtered.