We found our issue by checking the build logs for our most recently submitted build. For some unknown reason, the read app config step on the Android build showed that updates.url was missing. This was not the case on the iOS build (even though both builds were started at the same time, with the same config). We rebuilt and resubmitted the Android version to the store, and now the updates are working again.