Hola
Algo estás haciendo mal o algo no nos estás pegando del código. Ve despacio y con calma.
He tomado tu código, lo he pegado en un documento en blanco y he agregado la regla en la etiqueta style y se ve perfecto.
Fondo verde y el párrafo con un borde rojo.
Este es el código:
Código HTML:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>Esto es una prueba</title>
<link rel="stylesheet" href="estilo.css" type="text/css">
<style type="text/css">
body {color:black;background-color:#006600;font-family:Arial}
p { border: 1px solid #f00; }
</style>
</head>
<body>
<p>esta linea debe salir con borde rojo alrededor si todo va bien.</p>
<h1>Título de primer orden</h1>
<h2>Título de segundo orden</h2>
</body>
</html> Le agregué el doctype por cuestiones de hacer un código correcto, pero sin el también se ve.
Si te falla nuevamente, es que la hoja de estilos no existe, se llama diferente o tiene algo más que está haciendo que no se cargue o interprete bien.
Felicidad