I have been having the same problem as the OP for over a year. I am using Outlook (as part of Office XP) under Vista. However, note that this problem did not arise when I first installed Outlook under Vista.
Historically, at the end of each year I would use Outlook (from Office XP) to create a new PST file (as a calendar-year archive). This worked without problem until I tried to archive my 2007 mail at the start of 2008.
I would typically go to "File... Data File Management... Add..." and follow the obvious steps to create a new PST file.
However, on specifying the chosen filename, I now get the error "The requested operation failed.".
I also get the same error if I try to add an existing PST file to my Outlook. On specifying the existing PST file, which is not corrupted and has always worked in the past, the same error is generated.
Interestingly, I did not know about the "New... Outlook Data File..." option until I read your post. Intriguingly, this also fails at exactly the same step, but the error is slightly different: "The operation failed." The error box is also different - it is not a standard Vista error box with the text rendered/antialiased by Vista itself (as above), but is in simple-looking text apparently in the same format as the rest of Outlook.
Note that when I installed Outlook originally, I was able to use exactly this method to add 11 PST files to my Outlook, all of which are still there and working fine. Up until January 2008 I was able to create, add and remove PSTs at will from my Outlook. Since then I have been entirely unable to either create a fresh PST or add an existing PST to my Outlook.
I hope this is detailed enough to help, and that you can point me in the right direction.