I finally fixed this using the Google's camera app. It gets the phone's orientation by using a sensor and then sets the EXIF tag appropriately. The JPEG which comes out of the camera is not oriented automatically.
Also, the camera preview works properly only in the landscape mode. If you need your activity layout to be oriented in portrait, you will have to do it manually using the value from the orientation sensor.