My younger child was extremely unhappy at his last preschool after having been happy at a different one. He also said he was bored. It got very bad, to the point of crying many days before school. I could not find anything wrong about the environment, other than the fact that it was possibly a little too pre-academic, but they ha dplenty of puppets, blocks, kitchen play, etc. It was a miserable year and I was very worried about kindergarten. Lo and behold, K has been completely fine (he has a great teacher and does go to 1st part-time). It's not clear to me exactly why preschool was so bad, but there was apparently a mismatch somehow. I guess my only advice would be to go and observe.
