El memory_limit no tiene nada que ver con la capacidad de espacio en tu hosting. Se trata de la memoria máxima a la que puede acceder un script PHP. Puedes ver cuánta tienes asignada desde el menú Parámetros avanzados -> Información:
Si tienes más de 128M no debería ser el problema, a no ser que tengas un número realmente elevado de combinaciones en cada producto.
¿Has cambiado el "max_input_vars" y te sigue sin dejar guardar? ¿Cuánto tiempo tarda desde que le das al botón de guardar hasta que aparece el mensaje de error?