En mi Android 4.3.1:

• Abrir Mapas desde tu teléfono
• Deslizar el menú
• Seleccionar Ajustes
• Editar casa o trabajo

Solución más fácil:

• Haz clic en el botón en la parte superior izquierda que dice "Mapas"
• Selecciona "Mis sitios"
• Allí está el botón para "casa"
• Pulsa y mantén para obtener la opción de editarlo

Tuve el mismo problema pero no vi la interfaz gráfica de la que hablabas en mi Galaxy S3. Así es como lo hice:

1. Abrí Google Maps
2. Si estás en la pantalla de rutas/navegación, presiona el botón de retroceso hasta que regreses a la vista de mapa predeterminada con una barra de búsqueda en la parte superior.
3. La barra de búsqueda debería tener 2 iconos a la derecha: uno para rutas/navegación, y otro que parece un icono de usuario. Haz clic en el icono de usuario.
4. La pantalla debería mostrar tu nombre completo en la parte superior, tu imagen de usuario junto al número de reseñas que has escrito, y directamente debajo, tus direcciones de casa y trabajo. Mantén pulsado la dirección que quieres editar.
5. Debería aparecer una nueva pantalla con una caja de búsqueda en la parte superior, pero debería haber un icono de casa o trabajo en la parte izquierda de la caja de búsqueda. Simplemente escribe o busca tu dirección correcta y luego presiona "Listo".

Método Alternativo

1. Nuevamente, abre Google Maps y presiona el botón "atrás", si es necesario, para volver a la vista de mapas predeterminada.
2. Pulsa el botón "menú" en tu teléfono o simplemente toca la pestaña de menú en la esquina inferior izquierda. Esto debería hacer que aparezca un menú deslizable desde la izquierda.
3. Toca la opción "Configuración" y luego "Editar casa o trabajo".
4. Luego simplemente toca en el que quieres editar.

Si desea hacer esto en una computadora de escritorio, puede ir a maps.google.com, iniciar sesión con su cuenta de Google y hacer clic en Mis lugares en la izquierda. Esto muestra su dirección actual de Casa y Trabajo junto con un poco de historial de ubicación, y puede encontrar Editar bajo el menú desplegable junto a cada entrada.