mp3s could very well be replaced, it all depends on what format has the most support, heck thats how mp3s came to dominate in the first place. Ever notice that Mini Discs were taking over Japan the same time mp3s were starting to heat up in the US? All about support. Companies will usually try and pimp their own format - M$ has WMA, Real has their own, even Sony is trying to push the Atrac compression technology used with Mini Discs as their own compression format by offering Atrac support with their own mp3 CD players (and obviously its what their MD players use)
While there's high quality lossy formats such as Ogg Vorbis and Musepack, they aren't backed by companies, enthusiasts developed them and the only way they could take off is if thats what users want to use.
Otherwise the best bet for an mp3 replacement would be AAC, Apple and several others have shown support for the "mp4" format (naturally the uneducated would assume mp4 > mp3 but the standard hasn't even been hashed out as there's still a raw .aac or .m4a)
We shouldn't think along the lines of "what formats can hardware support" but rather "this is the format I want to listen to, I'll try to help promote it and wait for support to come".
I dunno, but I'd really like a player that could have support for just about whatever format has decent support behind it. A "winamp" portable player would definately kick ass.