GameTrailers.com now have the first trailer for the LEGO Batman game. Here's their page for the game with the links to QuickTime and Windows Media format trailers, as well as an "HD" version.