Tienes que hacer dos cosa en ese codigo:
1) Agregar
$Internet = $_POST['Internet'];
$Deportes = $_POST['Deportes'];
Por las dudas que los registros gloables esten off (lo recomiendo)
2) cambiar en el IF el OR por un AND, tu quieres mostrar error si no selecciono nada, o sea todos los check son distintos al valor ;)
Código PHP:
<?php
$Internet = $_POST['Internet'];
$Deportes = $_POST['Deportes'];
if( ($Internet!="Internet") AND ($Deportes!="Deportes") )
echo "Debes seleccionar al menos una categoría";
else
echo "Hicistes tu seleccion";
?>
Saludos