We never use this tool when building our DB's but agree to start with steps from asrujit_pb first.
Errors do look to be more connectivity related than permissions related but the error messages aren't always the best. Depending on whether you manage your own instance of SLQ Server or have a DBA it may be worth exploring this alternative option for creating your EGDB over the toolbox tools.
Build new DB in SQL Server and give it whatever name is desired (ex. GIS). Create the DBO account (ex. sde or GISAdmin) you wish to have own the new DB. Grant this account (GISAdmin) the DBO permission by setting: GISAdmin IS dbo statement. Create a new DB connection in ArcCatalog using the DB account GISAdmin. Right click on the new connection and go to "Enable Geodatabase". Process runs and essentially does what the ArcToolbox tools you showed are attempting to do except without having to use the SA account. Once the process has completed verify your connectivity to the EGDB. Go back into SQL Server and issue the change: GISAdmin AS dbo. You are all set to go but I'd also recommend at that point building and assigning your different schema's and schema owner accounts all within SQL.
