Try the -Force parameter:

New-Item -ItemType Directory -Force -Path C:\Path\That\May\Or\May\Not\Exist

You can use Test-Path -PathType Container to check first.

See the New-Item MSDN help article for more details.