Q:

strange maybe appearing in tuple type

I have the demonstrator code below that fails to compile with the error:
Occurs check: cannot construct the infinite type: p0 = Maybe p0
    Expected type: PSQ.PSQ (t1, t2, (t0, [a0])) (Maybe p0)
      Actual type: PSQ.PSQ (t1, t2, (t0, [a0])) p0
    In the third argument of `PSQ.insert', namely `q'
    In the expression: PSQ.insert test' time q

If I make the code from AppendMsg part of main it compiles.  If a try to make it a separate function it fails with the strange maybe related error.  I am not quite sure where the maybe type comes from.  I have tried to resolve it with e.g. let time = Just (PSQ.lookup test time) but no joy.  I have tried it without Data. Label/lenses but also no joy.  Even a very simple function to insert the additional message gives the same error. 
What could be wrong here? 
import Data. Time
import Data. Time. Clock. POSIX
import qualified Data. PSQueue as PSQ
import Data. Maybe
import Data. Label
import Control. Category
import Prelude hiding ((.)) 

test = ("192.168.1.1", 3455, (1234566, msgs))
msgs = ["aaa", "bbbb", "ccccc"]

second2 = lens (\(a,b) -> b)   (\b (a,_) -> (a,b))
third3  = lens (\(a,b,c) -> c) (\c (a,b,_) -> (a,b,c))
messages = second2 .  third3

append x = modify messages (x :)

newRq = do
      time <- getPOSIXTime
      let q = PSQ.singleton test time
      return q

appendMsg a q = do
      let time = PSQ.lookup test q
      let test' = append a test
      let q' = PSQ.insert test' time q
      let q = PSQ.delete test q' 
      return q

--insertNewRec a q = do 
--     time <- getPOSIXTime
--     let q' = PSQ.insert a time q
--     return q

main :: IO()
main = do
     q <- newRq
     let q' = appendMsg "first" q
     print (q')

Have revised appendMsg according to all comments/answers (see below).  It now compiles but execution ends with <<loop>> :-(. 
appendMsg :: String -> PSQ.PSQ (String, Integer, (Integer, [String])) POSIXTime -> PSQ. 
PSQ (String, Integer, (Integer, [String])) POSIXTime 
appendMsg a q = q
      where 
       Just time = PSQ.lookup test q
       test2 = append a test
       q' = PSQ.insert test2 time q
       q = PSQ.delete test q' 

A:

Apart from the dubious monadic type of appendMsg, instead of
let time = Just (PSQ.lookup test time)

(btw.  I suppose the second 'time' is a typo and was actually a 'q'), you should have tried
let Just time = PSQ.lookup test q

And I strongly recommend giving type signatures for your functions, that way GHC can give you much more helpful error messages since that way type errors are reported where they are made, and not where they cause type checking to fail. 
Edit: The reason for the <<loop>> in the revised code
appendMsg :: String -> PSQ.PSQ (String, Integer, (Integer, [String])) POSIXTime
          -> PSQ.PSQ (String, Integer, (Integer, [String])) POSIXTime 
appendMsg a q = q
  where 
   Just time = PSQ.lookup test q
   test2 = append a test
   q' = PSQ.insert test2 time q
   q = PSQ.delete test q'

is the circular dependency of q and q' in the where clause.  The bindings in a where clause (or a let) are recursive and can be arbitrarily ordered, so the qs in that all refer to the one bound in the last line, not the parameter - whoops.  In the original code you had multiple lets, so the bindings were not (mutually) recursive and a binding let x = ... shadowed any previous binding of the identifier x.
To break the <<loop>>, the easy and recommended fixes are

appendMsg a q = q'' and in the last line of the where clause q'' = PSQ.delete test q'
appendMsg a q = PSQ.delete test q' and remove the last line of the where clause

You can also build a let-tower
appendMsg a q =
    let Just time = ... in
    let test2 = ... in
    let q' = ... in
    let q = ... in q

but I don't recommend that. 

A:

PSQ.lookup has a Maybe a return type because the key you pass it might not actually be in your PSQ.  You want code that handles the possible error (unless you'd rather crash, or are sure it will never happen). 
Slightly modifying Daniel Fischer's answer..
let time = case PSQ.lookup test q of
             Just x -> x
             Nothing -> (...)

Where (...) can be a default value or perhaps error "I am a helpful error message" or something.