Multisite setup issues

I am trying to set up Multisite, but when I get to the subdomain/subdirectory option, I get no option and it defaults to subdomain.
I then have site details listed but when I click on mynewdomin.mysite.com it comes up with a server not found page.
The site is set up as http://mysite.com

Despite deleting previous WP installs (& database) I was given this msg in WP once I'd done a vanilla WP reinstall:

"Sub-domain Install
Because your install is not new, the sites in your WordPress network must use sub-domains. The main site in a sub-directory install will need to use a modified permalink structure, potentially breaking existing links."

Can anyone please assist?

Cheers
Colinz