Is this "new wallet" on the same computer? Please describe with a little more detail. So that the advice is specific to your exact situation, you might consider providing the Bitcoin addresses of these transactions.
For a new installation, until the client has downloaded all the blocks needed, it will not show new transactions.
- http://en.bitcoin.it/wiki/FAQ#I_was_sent_some_bitcoins_and_they_haven.27t_arrived_yet.21_Where_are_they.3F
What you are describing can happen when the same wallet is copied and run from two separate computers. When that happens, in certain instances an invalid transaction can be made and invalid transactions will not confirm and be left showing permanently as 0/unconfirmed. Without performing surgery to the wallet, there is no way to get the "0/uncofirmed" to go away, so spending the wallet's balance and starting fresh is probably the best suggestion if that is what is happening.
Rather than depending on the client to tell you what transactions have been processed, consider using the BlockExplorer. Once the transaction apears is in BlockExplorer, then you can know it was a valid transaction.