Turns out, I was using eglChooseConfig the wrong way. The fix was simple:

EGLint total_config_count;
success = eglChooseConfig(egl_display, config_attrs, NULL, 0, &total_config_count);
EGLConfig* all_configs = (EGLConfig*) malloc(sizeof(EGLConfig) * total_config_count);
success = eglChooseConfig(egl_display, config_attrs, all_configs, total_config_count, &total_config_count); //Changed the last argument from NULL

Hope this was useful!