Some visitors cannot access my website

I am receiving some reports from different clients in Spain, US and France that they cannot access my website, https://www.ultreyatours.com. They get a ERR_NAME_NOT_RESOLVED error saying the server cannot be found.

Personally, I do not get any error and most visitors don't experience it, but one of my clients has been kind enough to send me their traceroute outputs - below. He uses Google DNS in his browser.

I have a shared IP address which made me think it was blocked by an ISP, but it doesn't seem like it is the case. I have contacted Telefonica (which is the last server reached by my client) to ask if they blocked my IP address just in case, but it has been nine days and no response so far.

All website testing programs I've tried cannot seem to find the error. The only red flag I found was that my MX records points to a CNAME. But this is the standard mail settings of my host, Go Daddy.

Could anyone tell me if they cannot access the website and send me the traceroute or do you have any suggestions as to why this is happening? Should I change host just in case?

traceroute to ultreyatours.com (160.153.74.24), 64 hops max, 52 byte packets
 1  192.168.1.1 (192.168.1.1)  7.887 ms  2.594 ms  2.378 ms
 2  192.168.144.1 (192.168.144.1)  51.844 ms  42.309 ms  41.189 ms
 3  * * *
 4  26.red-80-58-89.staticip.rima-tde.net (80.58.89.26)  55.877 ms
    65.red-81-46-3.staticip.rima-tde.net (81.46.3.65)  54.211 ms
    26.red-80-58-89.staticip.rima-tde.net (80.58.89.26)  54.896 ms
 5  216.184.113.116.nuevatel.com (216.184.113.116)  51.841 ms  51.221 ms  51.849 ms
 6  xe0-0-0-8-grtlontlw1.red.telefonica-wholesale.net (94.142.125.246)  88.292 ms
    xe6-1-0-0-grtlontl1.net.telefonicaglobalsolutions.com (213.140.36.254)  94.572 ms
    xe-2-0-2-0-grtparix1.net.telefonicaglobalsolutions.com (94.142.117.174)  115.531 ms
 7  xe2-0-1-0-grtwaseq6.net.telefonicaglobalsolutions.com (94.142.116.209)  164.105 ms
    xe-3-1-4-0-grtwaseq6.red.telefonica-wholesale.net (213.140.36.242)  148.022 ms
    xe0-0-1-0-grtnycpt3.red.telefonica-wholesale.net (94.142.126.73)  185.685 ms
 8  xe-0-0-2-0-grtnycpt3.red.telefonica-wholesale.net (94.142.126.69)  150.588 ms
    dcp-brdr-03.inet.qwest.net (63.235.40.197)  157.253 ms  151.465 ms
 9  phn-edge-08.inet.qwest.net (67.14.40.50)  218.708 ms
    dcp-brdr-03.inet.qwest.net (63.235.40.197)  163.898 ms
    xe3-1-1-0-grtwaseq6.net.telefonicaglobalsolutions.com (5.53.6.145)  178.165 ms
10  xe6-0-6-0-grtwaseq6.net.telefonicaglobalsolutions.com (94.142.116.102)  183.294 ms
    phn-edge-08.inet.qwest.net (67.14.40.50)  218.202 ms
    63-232-81-254.dia.static.qwest.net (63.232.81.254)  235.276 ms
11  be39.trmc0215-01.ars.mgmt.phx3.gdg (184.168.0.73)  224.855 ms
    63-232-81-254.dia.static.qwest.net (63.232.81.254)  255.575 ms
    phn-edge-08.inet.qwest.net (67.14.40.50)  227.479 ms
12  be39.trmc0215-01.ars.mgmt.phx3.gdg (184.168.0.73)  230.942 ms
    be38.trmc0215-01.ars.mgmt.phx3.gdg (184.168.0.69)  230.278 ms
    63-232-81-254.dia.static.qwest.net (63.232.81.254)  235.399 ms
13  * * be39.trmc0215-01.ars.mgmt.phx3.gdg (184.168.0.73)  243.940 ms
14  * * be39.trmc0215-01.ars.mgmt.phx3.gdg (184.168.0.73)  239.542 ms
15  * * *
16  * * *
17  * * *
18  * * *
19  * * *
20  * * *
21  * * *
22  * * *
23  * * *
24  * * *
25  * * *
26  * * *
27  * * *
28  * * *
29  * * *
30  * * *
31  * * *
32  *

If I'm not mistaken, the problem is that your registrar has published DS records for your domain - that is, DNSSEC signing keys:

[me@risby player]$ dig ds ultreyatours.com
[...]
;; ANSWER SECTION:
ultreyatours.com.       85920   IN      DS      49864 8 1 0152C1213569799FAFA42C7699A20132A293F908
ultreyatours.com.       85920   IN      DS      20536 8 1 291A619699C18BF007CB937928EA99A81CC73314

but your A record is unsigned:

[me@risby player]$ dig www.ultreyatours.com +trace +dnssec
[...]
.                       487995  IN      NS      i.root-servers.net.
[...]
.                       487995  IN      RRSIG   NS 8 0 518400 20150919050000 20150909040000 1518 . m8MEJxwjDheKkuBXEMRTO+vqGHVFRznH45Tr8bT6iCb+0uulK3y5QLuA 627T5DJ65LbWlnTlM3QjFlSVkgO7d9Km5gLD9BJ6txuwyxlI2XR+BQmW GykfNbqpMpvvnaZpBu6UoIts7oP0TrvbvD8hePoGwBGE5gtnKWGV151z LFI=
;; Received 913 bytes from 127.0.0.1#53(127.0.0.1) in 0 ms
[...]
com.                    172800  IN      NS      m.gtld-servers.net.
com.                    86400   IN      DS      30909 8 2 E2D3C916F6DEEAC73294E8268FB5885044A833FC5459588F4A9184CF C41A5766
com.                    86400   IN      RRSIG   DS 8 1 86400 20150919050000 20150909040000 1518 . ktOAFoG5Ymb03TSau6Fu6HHdoo6T4tXmHEvXbX9aAbsy3JmEPirZtr2C 6ZJikjUc4AhTZ69aHhca1T3uoc2LwhuNbXdL6bSHTC+tdWnBNYE4wqXk USAfz2eCJSNG6MBIPclYxY8N9CvekmrTCWrFZpisv44dLqRPfxizUdX1 TQc=
;; Received 744 bytes from 193.0.14.129#53(k.root-servers.net) in 23 ms

ultreyatours.com.       172800  IN      NS      pdns05.domaincontrol.com.
ultreyatours.com.       172800  IN      NS      pdns06.domaincontrol.com.
ultreyatours.com.       86400   IN      DS      49864 8 1 0152C1213569799FAFA42C7699A20132A293F908
ultreyatours.com.       86400   IN      DS      20536 8 1 291A619699C18BF007CB937928EA99A81CC73314
ultreyatours.com.       86400   IN      RRSIG   DS 8 2 86400 20150913044955 20150906033955 35864 com. fCufZ3SGLfbzgEQHKuZm1kz77cJFoNyW0tZOSMvZhpYSHSxkVwcWSDlM knyJ+Fvh4+yekb/hqtn0BzBJE20GmRCUdd4DBqqRj7+Y8Ki0cUn52CFu Ii1mWS7XhtmR62AgZcUl+Z0CGSC8gxApUAS/H+jgQatOuGonnWIWp6pt UC8=
;; Received 372 bytes from 2001:503:231d::2:30#53(b.gtld-servers.net) in 29 ms

www.ultreyatours.com.   600     IN      A       160.153.74.24

Note the absence of an RRSIG record after your A record. That means that the chain of trust cannot be established, and though I get an answer back, my nameserver ignores it:

[me@risby player]$ dig www.ultreyatours.com

; <<>> DiG 9.10.2-P3-RedHat-9.10.2-4.P3.fc22 <<>> www.ultreyatours.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: SERVFAIL, id: 57573
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 4096
;; QUESTION SECTION:
;www.ultreyatours.com.          IN      A

;; Query time: 1944 msec
;; SERVER: 127.0.0.1#53(127.0.0.1)
;; WHEN: Wed Sep 09 14:47:03 BST 2015
;; MSG SIZE  rcvd: 49

I suspect the problem happens with those clients who are checking DNSSEC signatures, for they will certainly get name not resolved errors.

Note that the traceroute output above is highly-misleading; they have tried to traceroute to ultreyatours.com, which does have an RRSIG:

ultreyatours.com.       600     IN      A       160.153.74.24
ultreyatours.com.       600     IN      RRSIG   A 8 2 600 20150924120914 20150909120914 8274 ultreyatours.com. ToF8G2xBluSzGVVbjXA02wIOodSrvzTHmFPwYwupeeDDmVC4nXgZbmzK 4RGICA0sZhU8dionVySlDPErD8GBMegOB/vjW77DgVLP0BYY3STA5m0y annQ/AUjTq0boyFj2aYmHSu0mfTnu/TkMgjkV/cDIekCC1LfeoNruFxF N4w=

and which resolves correctly in the output you show above. I must urge you to be very precise in investigating this sort of issue; clients who report resolution problems with one hostname do you no favours when they try to traceroute to another.

Edit: I can confirm that you've turned off DNSSEC for your domain: dig ds ultreyatours.com @a.gtld-servers.net no longer produces any records. Hopefully, in less than a day your cached DS records will age out, and your DNS will start working again, even for DNSSEC-aware clients.