You can create a new service using automator (from the applications folder). At the top of the automator window, enter: Service receives 'no input' in 'any application'. Then, in the workflow, add 'Run applescript'. Make the applescript contain the following:
on run {input, parameters}
tell application "Terminal"
do script ""
activate
end tell
return input
end run
(You can add any command you like into the do script line between the " " (e.g. something useful to run when terminal first opens like uptime
if you like, or just leave it blank).
Save the service as 'Open Terminal' or whatever name you like. It should now appear in your services menu.
Then if you want to add a keyboard shortcut, you just need to go to System Preferences -> Keyboard -> Keyboard Shortcuts tab, select services in the left hand menu, and find your new service (its probably near the bottom). Just click in the space to the right of your service name, and assign it whatever keyboard shortcut you like, and hey presto! it should all work