Hi Evan,
Do you remember making any changes to the computer prior to this issue?
I suggest you to try the methods given below and check if it helps.
Method 1:
Follow these steps to turn on All Messaging Service in Messaging app.
a) Open Messaging app and press Windows key + C to open the Charms Bar.
b) Click on Settings and then Options.
c) Click on Send and Receive Messages.
d) Make sure that the option All Messaging Service is turned on.
You may also try disabling Proxy server if it is enabled.
Method 2: Disable the proxy server and check.
a) Open Internet Explorer
b) Click Tools and then click Internet Options.
c) Then click the Connections tab.
d) Then click the LAN Settings button.
e) Then Uncheck the option which reads” Use a proxy server for your LAN”
f) Click on apply and then ok.
We may also try disabling third party security software.
Method 3: Disable third-party Security Software.
a) On your Computer screen Task Bar next to System Clock..
b) You will see the third-party Security Software Icon.
c) Click on the third-party Security Software Icon, you will see a pop up.
d) In that pop and select the option to disable, click on it.
Now the third-party Security Software will be disabled.
Important Note: Antivirus software can help protect your computer against viruses and other security threats. In most cases, you shouldn't disable your antivirus software. If you have to temporarily disable
it to install other software, you should re-enable it as soon as you're done. If you're connected to the Internet or a network while your antivirus software is disabled, your computer is vulnerable to attacks.
Also refer to the article given below.
Messaging app for Windows: Frequently asked questions
http://windows.microsoft.com/is-is/windows-8/messaging-faq
Reply back if the issue persists, we are here to assist you.