Ese error es porque no existe el campo estado en tu update.
Dim UpdateCmd As String = "UPDATE Ciudad SET Nombre_Ciudad = @Nombre_Ciudad,
Estado 
= @Estado Where CiudadID= @CiudadID"
Por lo que veo en tu estructura el campo Estado pertence a la tabla Estado no..?? que mas bien sería Estado.Nombre_Estado, pero estas haciendo un update sobre una tabla.. y debería ser en las dos o no.??