Nobody can tell you anything without exact info on comp settings, render settings and so on. It simply sounds like you are using a specific encoding preset that has fixed constraints.
I know! don't understand it! for some reason I can't find this encoding preset, it seems set on 740x480 and its impossible to see where or why.
It refuses me to update as well, both AE and the media encoder.
Oh well I will simply have to use Premiere instead,
thanks for your post.