I remember seeing a movie when I was younger, but can't find it online because I can't remember a whole lot about the story. What I do remember is there was a group of soldiers trying to catch this castle that appeared only during the day and at the start of each new day it would teleport to a new random location. I also remember the main character having this neat little flying blade disk that reminds me of something from the Predator movies that he could control with his mind. Again I can't recall a lot about the movie, but if it sounds familiar I would be grateful. Also it seems like at one point there were horses that ran so fast they caught fire!
The movie you are looking for is Krull.
Prince Colwyn is found and nursed by Ynyr, the Old One. Ynyr tells him the Beast can be defeated with the "Glaive", an ancient, magical, five-pointed throwing weapon. Colwyn retrieves the Glaive from a high mountain cave before setting out to track down the Black Fortress, which teleports to a new location every day at sunrise. As they travel, Colwyn and Ynyr are joined by magician Ergo "the Magnificent" and a band of nine thieves, fighters, bandits and brawlers. Colwyn offers to clear their criminal records, successfully enlisting Torquil, Kegan, Rhun, Oswyn, Bardolph, Menno, Darro, Nennog, and Quain. The cyclops Rell later joins the group.
The Fire Mares, steeds that travel so fast they leave a trail of flame and can effectively fly, are played by Clydesdale horses.
The bad guys travel the galaxy in a mountain-like spaceship called The Black Fortress, which teleports to a new location every sunrise. The heroes ride Fire Mares, horses so fast they leave a trail of flames in an attempt to catch up with it.
The 'neat flying blade disk' is called a (or perhaps 'the') Glaive and can be seen on what appears to be the DVD cover.